МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ    XII

§ 264. Замечание к методу математической индукции

Доказательство методом математической индукции состоит из двух этапов.

1-й этап. Проверяем, верно ли утверждение при п = 1 (или при п = р, если речь идет о методе, описанном в § 263).

2-й этап. Допускаем, что утверждение верно при п = k, и, исходя из этого, доказываем, что оно верно и при п = k + 1.

Каждый из этих этапов по-своему важен. В § 261, рассматривая пример f (n) =  n² + п + 41, мы убедились, что утверждение может быть верным в целом ряде частных случаев, но неверным вообще. Этот пример убеждает нас в том, насколько важен 2-й этап доказательства методом математической индукции. Опустив его, можно прийти к неверному выводу.

Не следует, однако, думать, что 1-й этап менее важен, чем 2-й. Сейчас мы приведем пример, показывающий, к какому нелепому выводу можно прийти, если опустить 1-й этап доказательства.

«Теорема». При любом натуральном п число 2п +1 четное.

«Доказательство». Пусть эта теорема верна при п = k, то есть число 2k + 1 четное. Докажем, что тогда число 2(k + 1) +1 также четно.

Действительно,

2(k + 1) + 1 = (2k + 1) + 2.

По предположению число 2k + 1 четно, а поэтому его сумма с четным числом 2 также четна. Теорема «доказана».

Если бы мы не забыли проверить, верна ли наша «теорема» при п = 1, мы не пришли бы к такому «результату».