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


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

§

Не знаю, кто его придумал! Где-то читал, что Паскаль — для доказательства формулы бинома Ньютона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) Хотя сам парадокс был известен гораздо раньше.

2017/04/04 22:48 редактировал au