Этот метод применяется для доказательства утверждений, зависящих от параметра, принимающего натуральные значения; целью ставится доказать справедливость утверждения при всех значениях параметра.

Пример. Доказать справедливость формулы

$$ 1+2+\dots+n=\frac{n(n+1)}{2} $$ при всех натуральных $ n_{} $.

При каждом частном значении $ n_{} $ формулу можно проверить, но как совершить «переход к бесконечности» — сделать вывод о справедливости формулы для всего бесконечного набора значений $ n_{} $?

Для этого и используется метод математической индукции, который заключается в следующем: пусть имеется некоторое утверждение A , зависящее от параметра $ n_{} $, принимающего значения из $ \mathbb N $. Будем обозначать это утверждение А $ (n) $.

1. Проверяем справедливость утверждения А $ (1) $ (этот пункт называется базисом индукции).

2. Выдвигаем предположение о справедливости утверждения А $ (k) $ при $ k_{}>1 $ (индукционное предположение).

3. На основании индукционного предположения доказываем утверждение А $ (k+1) $ (индукционное заключение).

Если это удается осуществить, то делаем вывод, что утверждение А $ (n) $ справедливо для всех натуральных чисел $ n_{} $.

Проиллюстрируем работу метода на примере формулы суммы первых $ n_{} $ натуральных чисел. При $ n_{}=1 $ она, очевидно, верна. Пусть справедлива формула $$1+2+\dots+k=\frac{k(k+1)}{2} \ . $$ Тогда на ее основании выводим $$1+2+\dots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2} \ , $$ т.е. формула остается справедливой и при $ n=k+1 $. Следовательно она справедлива при всех $ n \in \mathbb N $.

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

$$1^3+2^3+\dots+n^3=(1+2+\dots+n)^2 \ ; $$ $$ 1 \cdot 1!+2\cdot 2!+3\cdot 3!+\dots+n\cdot n!=(n+1)! -1 \ $$ при $ n \in \mathbb N $.

Пример. Доказать неравенство

$$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n}< \frac{1}{\sqrt{n}} \ npu \ n \in \mathbb N \ . $$

Решение. Справедливость для $ n=1_{} $ очевидна. Предположим, что оно верно для некоторого $ n> 1 $, нужно показать справедливость неравенства $$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n} \cdot \frac{2n+1}{2n+2}< \frac{1}{\sqrt{n+1}} \ . $$ Домножаем неравенство индукционного предположения на дробь $ (2n+1)/(2n+2) $, получаем: $$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n} \cdot \frac{2n+1}{2n+2}< \frac{2n+1}{2n+2} \frac{1}{\sqrt{n}} \ . $$ Для того, чтобы прийти к неравенству индукционного заключения, достаточно показать, что $$ \frac{2n+1}{2n+2} \frac{1}{\sqrt{n}} \le \frac{1}{\sqrt{n+1}} \ . $$ Это неравенство эквивалентно следующему: $$ (2n+1) \sqrt{n+1} \le 2(n+1) \sqrt{n} \ ; $$ возведение в квадрат приводит к: $$ (2n+1)^2(n+1) \le 4(n+1)^2 n \qquad \iff \qquad (n+1)((2n+1)^2- 4(n+1) n) \le 0 \ \iff $$ $$ \iff \qquad n+1 \le 0 \ . $$ Последнее, очевидно, неверно.

Попробуем доказать методом математической индукции более сильное утверждение $$ \frac{1}{2} \cdot \frac{3}{4} \times \dots \times \frac{2n-1}{2n}< \frac{1}{\sqrt{n+1}} \ , $$ следствием которого будет доказываемое выше. Кажется, что мы должны прийти к тому же противоречию. Однако на этот раз метод осечки не дает. Для $ n=1_{} $ неравенство очевидно справедливо. Предположим, что оно справедливо для какого-то $ n>1 $. Домножим его на $ (2n+1)/(2n+2) $ и проверим выполнимость неравенства $$ \frac{2n+1}{2n+2} \frac{1}{\sqrt{n+1}} \le \frac{1}{\sqrt{n+2}} \ . $$ Имеем: $$ (2n+1) \sqrt{n+2} \le (2n+2) \sqrt{n+1} \qquad \iff \qquad (2n+1)^2 (n+2) \le (2n+2)^2 (n+1) \ \iff $$ $$ \iff 0 \le 3\,n+2 \ , $$ что справедливо. ♦

Итак, исходное неравенство справедливо, но доказать его методом математической индукции не удается, хотя более сильное утверждение — удается! Такая ситуация называется парадоксом изобретателя, это название было придумано в XX веке венгерским математиком Д.Пойа¹⁾. Противоречие разрешается следующим соображением: если утверждение А $ (n) $ слабее утверждения B $ (n) $, то и индукционные предположения, которые применяются в ходе доказательства, также будут находиться в том же соотношении — фактически мы получаем больший исходный ресурс для вывода индукционного заключения.

[1]. Bussey W.H. The Origin of Mathematical Induction. Amer. Math. Monthly, 1917, Vol. 24, No 5, 199-207. Текст ☞ the_origin_of_mathematical_induction.pdf (pdf).