Математическая индукция

Определение

Индукция доказывает, что свойство $P(n)$P(n) выполняется для всякого целого начиная с номера $n_0$n0​, всего двумя проверками:

Эти два пункта устанавливают бесконечно много утверждений. В этом их сила: проверяются всегда лишь один случай и одна импликация.

Образ и его предел

Ряд домино: опрокинуть первую костяшку и обеспечить, чтобы каждая роняла следующую, довольно, чтобы упали все.

Образ верен в механизме и неверен в охвате. Ряд домино конечен, и падение занимает время; индукция касается бесконечно многих номеров и не разворачивается во времени. Она не повествует о распространении, она доказывает свойство.

Пример, доведённый до конца

Покажем, что сумма первых $n$n целых чисел равна $\dfrac{n(n+1)}{2}$2n(n+1)​.

База. При $n = 1$n=1: сумма равна 1, и $\dfrac{1 \times 2}{2} = 1$21×2​=1.

Переход. Пусть формула верна для номера $n$n. Тогда:

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

Это формула для номера $n+1$n+1. Оба шага выполнены, значит свойство верно при всяком $n \geq 1$n≥1.

Оба шага необходимы

Один переход не доказывает ничего. Возьмём $P(n)$P(n): «$n = n + 1$n=n+1».

Это свойство наследственно: если $n = n+1$n=n+1, то прибавив по 1 к обеим частям, получим $n + 1 = n + 2$n+1=n+2. Шаг распространяется безупречно — а свойство ложно при всяком целом, потому что ни один номер его не начинает.

Одной базы тоже мало: свойство может быть верным при 1 и ложным дальше.

Сильная индукция

Иным доказательствам нужен не только предыдущий номер. Сильная индукция предполагает $P(k)$P(k) для всех $k \leq n$k≤n, а не для одного $n$n.

Она нужна, когда переход обращается к гораздо более раннему номеру: разложение целого на простые множители отсылает к двум произвольным меньшим множителям, а не к предшественнику.

Итог

Отправная точка и распространяющийся шаг доказывают бесконечно много случаев; ни от одного нельзя отказаться.