Указатель — Разделы— Обозначения — Автор — О проекте

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

§

Не знаю, кто его придумал! Где-то читал, что Паскаль — для доказательства формулы бинома Ньютона 1).

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

П

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

$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$ .

§

Метод математической индукции — мощное, но не всесильное средство доказательства. Известны примеры истинных утверждений А $(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 веке венгерским математиком Д.Пойа2). Противоречие разрешается следующим соображением: если утверждение А $(n)$ слабее утверждения B $(n)$ , то и индукционные предположения, которые применяются в ходе доказательства, также будут находиться в том же соотношении — фактически мы получаем больший исходный ресурс для вывода индукционного заключения.

§

Иногда, ввиду особенности утверждения А $(n)$ , утверждение А $(1)$ не имеет смысла, тогда в качестве базиса индукции рассматривается утверждение А $(2)$ . В дальнейшем подобные модификации метода математической индукции будем применять без излишних комментариев.

1) Увидите подходящую ссылку — сообщите, пожалуйста.

2) Хотя сам парадокс был известен гораздо раньше.