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

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

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

Точное описание

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

Допустим, что Установлено, что P1 верно. (Это утверждение называется базой индукции.) Для любого n доказано, что если верно Pn, то верно Pn + 1. (Это утверждение называется индукционным переходом.) Тогда все утверждения нашей последовательности верны.

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

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

Пусть имеется последовательность утверждений $P_1,P_2, P_3 \ldots$. Допустим, что Установлено, что P1 верно. Для любого натурального n доказано, что если верны все $P_1,P_2, P_3 \ldots P_n$, то верно и Pn + 1. (Это утверждение называется индукционным переходом.) Тогда все утверждения в этой последовательности верны.

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

Примеры

Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство

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

Доказательство. Индукция по n.

База, n = 1:

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

Переход: предположим, что

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

тогда

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

$=\frac{1-q^{n+1}+(1-q)q^{n+1}}{1-q}=\frac{1-q^{n+1}+q^{n+1}-q^{(n+1)+1}}{1-q}=\frac{1-q^{(n+1)+1}}{1-q}$,

что и требовалось доказать.

Комментарий: верность утверждения P_n в этом доказательстве — то же, что верность равенства

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

См. также

• Доказательство одноцветности всех лошадей.

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

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

Литература

• Н. Я. Виленкин Индукция. Комбинаторика. Пособие для учителей. М., Просвещение, 1976.—48 с
• Л. И. Головина, И. М. Яглом Индукция в геометрии, «Популярные лекции по математике», Выпуск 21, Физматгиз 1961.—100 с.
• Р. Курант, Г. Роббинс «Что такое математика?» Глава I, § 2.
• И. С. Соминский Метод математической индукции. «Популярные лекции по математике», Выпуск 3, Издательство «Наука» 1965.—58 с.