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

Зачем это нужно

Проверив формулу для $n = 1, 2, 3, \ldots, 100$, мы всё ещё не знаем, верна ли она при $n = 101$. Многие утверждения выглядят верными на первых примерах, а потом ломаются. Например, выражение $n^2 + n + 41$ даёт простые числа при $n = 0, 1, \ldots, 39$, но при $n = 40$ получается $1681 = 41^2$. Чтобы доказать утверждение сразу для всех натуральных $n$, используют метод математической индукции. На нём держатся формулы сумм, свойства прогрессий, многие неравенства и правильность компьютерных алгоритмов.

Принцип индукции

Пусть $P(n)$ — утверждение, зависящее от натурального $n$. Если

1. база: $P(1)$ верно;
2. шаг: из того, что $P(k)$ верно (это предположение индукции), следует, что верно $P(k + 1)$,

то $P(n)$ верно для всех натуральных $n$.

Аналогия с домино точна: нужно и толкнуть первую костяшку (база), и расставить их так, чтобы каждая роняла следующую (шаг). Без любого из двух условий вывод неверен: если не толкнуть первую костяшку, ничего не упадёт. База может начинаться и не с единицы: например, утверждение «$2^n > n^2$» верно начиная с $n = 5$.

Доказательство формул

Разобранный пример 1

Докажите, что $1 + 2 + \ldots + n = \frac{n(n + 1)}{2}$.

1. База: $n = 1$: $1 = \frac{1 \cdot 2}{2}$ — верно.
2. Предположение: $1 + 2 + \ldots + k = \frac{k(k + 1)}{2}$.
3. Шаг: $1 + \ldots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2}$ — это формула для $n = k + 1$. ∎

Разобранный пример 2

Докажите, что $1 + 3 + 5 + \ldots + (2n - 1) = n^2$.

База: $1 = 1^2$. Шаг: $k^2 + (2k + 1) = (k + 1)^2$. ∎ Геометрически: квадрат $k \times k$ дополняется «уголком» из $2k + 1$ клеток до квадрата $(k + 1) \times (k + 1)$.

Делимость

Разобранный пример 3

Докажите, что $7^n - 1$ делится на 6 при всех натуральных $n$.

1. База: $7 - 1 = 6$.
2. Шаг: $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(7^k - 1) + 6$. Первое слагаемое делится на 6 по предположению, второе — очевидно. ∎

Неравенства

Разобранный пример 4 (неравенство Бернулли)

Докажите, что $(1 + x)^n \ge 1 + nx$ при $x > -1$ и натуральном $n$.

База $n = 1$: равенство. Шаг: $(1 + x)^{k+1} = (1 + x)^k(1 + x) \ge (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2 \ge 1 + (k + 1)x$. Мы умножали на положительное $1 + x$, поэтому знак сохранился. ∎

Разобранный пример 5

Докажите, что $2^n > n^2$ при $n \ge 5$.

База: $32 > 25$. Шаг: $2^{k+1} = 2 \cdot 2^k > 2k^2$. Осталось показать $2k^2 \ge (k + 1)^2$, то есть $k^2 - 2k - 1 \ge 0$ — это верно при $k \ge 3$. ∎ При $n = 2, 3, 4$ неравенство неверно, поэтому база важна.

Как оформлять доказательство

1. Сформулируйте утверждение $P(n)$ и укажите, с какого $n$ оно доказывается.
2. База. Подставьте наименьшее $n$ и проверьте утверждение явно.
3. Предположение. Запишите $P(k)$ — это не то, что доказываем, а то, чем разрешено пользоваться.
4. Шаг. Запишите цель $P(k + 1)$ и выделите в ней часть, совпадающую с $P(k)$. Для сумм это сумма первых $k$ слагаемых, для делимости — выражение $a^k$ в составе $a^{k+1}$, для неравенств — множитель или слагаемое.
5. Вывод. По принципу математической индукции $P(n)$ верно для всех $n$, начиная с базы.

Геометрическая задача

Разобранный пример 6

Докажите, что у выпуклого $n$-угольника $\frac{n(n - 3)}{2}$ диагоналей ($n \ge 3$).

База: у треугольника $\frac{3 \cdot 0}{2} = 0$ диагоналей. Шаг: добавив к $k$-угольнику новую вершину между двумя соседними, мы получим из прежней стороны новую диагональ и проведём из новой вершины ещё $k - 2$ диагонали. Всего $\frac{k(k - 3)}{2} + 1 + (k - 2) = \frac{(k + 1)(k - 2)}{2}$, а это формула для $n = k + 1$. ∎

Где ошибаются: «все лошади одного цвета»

Известный «парадокс»: докажем, что в любом табуне все лошади одной масти. База: одна лошадь — одной масти. Шаг: в табуне из $k + 1$ лошади уберём первую — остальные $k$ одной масти; уберём последнюю — снова $k$ одной масти; значит, все одной масти. Ошибка в шаге от $k = 1$ к $k = 2$: два множества по одной лошади не пересекаются, и вывод «все одной масти» не следует. Шаг должен работать для каждого $k$, начиная с базы.

Немного истории

Идею индукции использовал ещё Евклид при доказательстве бесконечности простых чисел, а явно метод сформулировали Франческо Мавролико (1575) и Блез Паскаль (1654). Название «математическая индукция» предложил Огастес де Морган в 1838 году.

Типичные ошибки

• Пропускать базу и проверять только шаг.
• В шаге доказывать $P(k + 1)$, не используя предположение $P(k)$.
• Путать «проверили для многих $n$» с доказательством.
• Начинать базу не с того $n$, с которого утверждение верно.
• Делать шаг, верный не при всех $k$ (как в «парадоксе» о лошадях).

Что дальше

• Комбинаторные тождества и биномиальные суммы — комбинаторные тождества, многие доказываются индукцией.
• Множества, логика, отображения — множества, логика и строгие доказательства в анализе.