Математическая индукция — метод математического доказательства , который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел . Для этого сначала проверяется истинность утверждения с номером ${\displaystyle 1}$ — база (базис) индукции, а затем доказывается, что если верно утверждение с номером ${\displaystyle n}$ , то верно и следующее утверждение с номером ${\displaystyle n+1}$ — шаг индукции, или индукционный переход.

Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино . Пусть какое угодно число косточек домино выставлено в ряд таким образом, что каждая косточка, падая, обязательно опрокидывает следующую за ней косточку (в этом заключается индукционный переход). Тогда, если мы толкнём первую косточку (это база индукции), то все косточки в ряду упадут.

Формулировка

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами : ${\displaystyle P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots }$ .

Допустим, что

1. Установлено, что ${\displaystyle P_{1}}$ верно. (Это утверждение называется базой индукции .)
2. Для любого ${\displaystyle n}$ доказано, что если верно ${\displaystyle P_{n}}$ , то верно ${\displaystyle P_{n+1}}$ . (Это утверждение называется индукционным переходом .)

Тогда все утверждения нашей последовательности верны.

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

Принцип полной математической индукции

Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:

Пусть имеется последовательность утверждений ${\displaystyle P_{1}}$ , ${\displaystyle P_{2}}$ , ${\displaystyle P_{3}}$ , ${\displaystyle \ldots }$ . Если для любого натурального ${\displaystyle n}$ из того, что истинны все ${\displaystyle P_{1}}$ , ${\displaystyle P_{2}}$ , ${\displaystyle P_{3}}$ , ${\displaystyle \ldots }$ , ${\displaystyle P_{n-1}}$ , следует также истинность ${\displaystyle P_{n}}$ , то все утверждения в этой последовательности истинны, то есть ${\displaystyle (\forall n\in {\mathbb {N} }){\Big (}(\forall i\in \{1;\dots ;n-1\})P_{i}\Rightarrow P_{n}{\Big )}\Rightarrow (\forall n\in {\mathbb {N} })P_{n}}$ .

В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при ${\displaystyle n=1}$ условие ${\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\Rightarrow P_{n}}$ в точности эквивалентно ${\displaystyle P_{1}}$ (его истинности не из чего следовать). Однако зачастую доказывать индукционный переход для ${\displaystyle P_{1}}$ всё равно приходится отдельно, так что разумно бывает выделить эту его часть в качестве базы.

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

Также он является прямым применением более сильной трансфинитной индукции .

История

Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду , хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида . Современное название метода было введено де Морганом в 1838 году .

Примеры

Сумма геометрической прогрессии. Доказать, что, каковы бы ни были натуральное ${\displaystyle n}$ и вещественное ${\displaystyle q\neq 1}$ , выполняется равенство

${\displaystyle \sum _{i=0}^{n}q^{i}\equiv 1+q+q^{2}+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}$

Доказательство. Индукцией по ${\displaystyle n}$ для произвольного ${\displaystyle q}$ .

Докажем базу индукции для ${\displaystyle n=1}$ :

${\displaystyle 1+q={\frac {(1-q)(1+q)}{1-q}}={\frac {1-q^{1+1}}{1-q}}.}$

Докажем переход : предположим, что для ${\displaystyle n=k}$ выполнено

${\displaystyle 1+q+\cdots +q^{k}={\frac {1-q^{k+1}}{1-q}},}$

тогда для ${\displaystyle n=k+1}$ , согласно предположению:

${\displaystyle 1+q+\cdots +q^{k}+q^{k+1}={\frac {1-q^{k+1}}{1-q}}+q^{k+1}=}$

${\displaystyle ={\frac {1-q^{k+1}+(1-q)q^{k+1}}{1-q}}={\frac {1-q^{k+1}+q^{k+1}-q^{(k+1)+1}}{1-q}}={\frac {1-q^{(k+1)+1}}{1-q}}}$ .

Значит по принципу математической индукции выполнено равенство для всякого ${\displaystyle n}$ . Что и требовалось доказать.

Комментарий: истинность утверждения ${\displaystyle P_{n}}$ в этом доказательстве — то же, что истинность равенства

${\displaystyle 1+q+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}$

Важные примеры: неравенство Бернулли , бином Ньютона .

Вариации и обобщения

• Обратная индукция
• Структурная индукция
• Трансфинитная индукция

См. также

• Математический софизм#Доказательство по индукции
  • Доказательство одноцветности всех лошадей

Примечания

Литература

• А. Шень. . — МЦНМО , 2004. — 36 с.
• Н. Я. Виленкин . Индукция. Комбинаторика. — Пособие для учителей. — М. : Просвещение, 1976. — 48 с.
• Л. И. Головина, И. М. Яглом . . — Физматгиз , 1961. — Т. 21. — 100 с. — ( Популярные лекции по математике ).
• Р. Курант , Г. Роббинс. Глава I, § 2 //
• И. С. Соминский. . — Наука, 1965. — Т. 3. — 58 с. — ( Популярные лекции по математике ).

Ссылки

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