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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Dominoeffect.png

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

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

Формулировка[править | править вики-текст]

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

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

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

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


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

Принцип полной математической индукции[править | править вики-текст]

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

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

В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при n=1 импликация (\forall i\in\{1;\dots;n-1\})P_i\longrightarrow P_n эквивалентна P_1. Принцип полной математической индукции является прямым применением более сильной трансфинитной индукции.

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

История[править | править вики-текст]

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

Примеры[править | править вики-текст]

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

1 + q + q^2 +\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}.

2 способ:

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

База, n = 1

1 + q = q + 1

Переход: n = k, надо доказать для k + 1

Доказательство:

1 + q + q^2 + ... + q^{k+1} = \frac{1 - q^{k+2}}{1-q}
1 + q + q^2 + ... + q^k = \frac{1 - q^{k+2}}{1-q} - q^{k+1}
1 + q + q^2 + ... + q^k = \frac{1 - q^{k+2} - q^{k+1} * (1-q)}{1-q}
1 + q + q^2 + ... + q^k = \frac{1 - q^{k+1}}{1 - q}
n = k, следовательно утверждение верно

Вариации и обобщения[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Nachum L. Rabinovih Раби Леви бен Гершом и происхождение метода математической индукции = Rabbi Levi ben Gershom and the origins of mathematical induction // Archive for History of Exact Sciences. — 1970. — В. 6. — С. 237-248.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]

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