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

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: ${\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}}$. (Это утверждение называется индукционным переходом.)

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

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

Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида[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 с. — (Популярные лекции по математике).

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