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

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

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

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: .

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

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

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

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

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

История

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

Примеры

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

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

База, n = 1:

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

тогда

,

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

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

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

• Трансфинитная индукция
• Структурная индукция
• Обратная индукция или Индукция Коши

Примечания

Литература

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