Указатель — Разделы— Обозначения — Автор — О проекте
Не знаю, кто его придумал! Где-то читал, что Паскаль — для доказательства формулы бинома Ньютона1).
Этот метод применяется для доказательства утверждений, зависящих от параметра, принимающего натуральные значения; целью ставится доказать справедливость утверждения при всех значениях параметра.
Пример. Доказать справедливость формулы
при всех натуральных .
При каждом частном значении формулу можно проверить, но как совершить «переход к бесконечности» — сделать вывод о справедливости формулы для всего бесконечного набора
значений
?
Для этого и используется метод математической индукции, который заключается в следующем: пусть имеется некоторое утверждение
A
, зависящее
от параметра , принимающего значения из
. Будем обозначать это
утверждение
А
.
1.
Проверяем справедливость утверждения
А
(этот пункт называется базисом индукции).
2.
Выдвигаем предположение о справедливости утверждения
А
при
(индукционное предположение).
3.
На основании индукционного предположения доказываем утверждение
А
(индукционное заключение).
Если это удается осуществить, то делаем вывод, что утверждение
А
справедливо для всех натуральных чисел
.
Проиллюстрируем работу метода на примере формулы суммы первых натуральных чисел.
При
она, очевидно, верна. Пусть справедлива формула
Тогда на ее основании выводим
т.е. формула остается справедливой и при .
Следовательно она справедлива при всех
.
Доказать справедливость формул
при .
Метод математической индукции — мощное, но не всесильное средство доказательства. Известны примеры истинных утверждений
А
, справедливость которых не может быть установлена
этим методом.
Пример. Доказать неравенство
Решение. Справедливость для очевидна. Предположим, что оно верно для некоторого
, нужно показать справедливость неравенства
Домножаем неравенство индукционного предположения на дробь , получаем:
Для того, чтобы прийти к неравенству индукционного заключения, достаточно показать, что
Это неравенство эквивалентно следующему:
возведение в квадрат приводит к:
Последнее, очевидно, неверно.
Попробуем доказать методом математической индукции более сильное утверждение
следствием которого будет доказываемое выше. Кажется, что мы должны прийти к тому же противоречию. Однако на этот раз метод осечки не дает. Для неравенство очевидно справедливо. Предположим,
что оно справедливо для какого-то
. Домножим его на
и проверим выполнимость неравенства
Имеем:
что справедливо. ♦
Итак, исходное неравенство справедливо, но доказать его методом математической индукции не удается, хотя более сильное утверждение — удается! Такая ситуация называется парадоксом изобретателя, это название было придумано в XX веке венгерским математиком Д.Пойа2). Противоречие разрешается следующим соображением: если утверждение
А
слабее утверждения
B
, то и индукционные предположения, которые применяются в ходе доказательства, также будут находиться в том же соотношении — фактически мы получаем больший исходный ресурс для вывода индукционного заключения.
Иногда, ввиду особенности утверждения
А
,
утверждение
А
не имеет смысла, тогда в качестве базиса индукции
рассматривается утверждение
А
. В дальнейшем подобные модификации
метода математической индукции будем применять без излишних комментариев.