Математическая индукция
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино. Пусть какое угодно число косточек домино выставлено в ряд таким образом, что каждая косточка, падая, обязательно опрокидывает следующую за ней косточку (в этом заключается индукционный переход). Тогда, если мы толкнём первую косточку (это база индукции), то все косточки в ряду упадут.
Содержание
Формулировка
Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: <math>P_1, P_2, \ldots, P_n, P_{n+1}, \ldots</math>.
Допустим, что
Тогда все утверждения нашей последовательности верны. |
Логическим основанием для этого метода доказательства служит так называемая аксиома индукции, пятая из аксиом Пеано, определяющих натуральные числа. Верность метода индукции эквивалентна тому, что в любом непустом подмножестве натуральных чисел существует минимальный элемент.
Принцип полной математической индукции
Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:
Пусть имеется последовательность утверждений <math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>\ldots</math>. Если для любого натурального <math>n</math> из того, что истинны все <math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>\ldots</math>, <math>P_{n-1}</math>, следует также истинность <math>P_n</math>, то все утверждения в этой последовательности истинны, то есть <math>(\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</math>. |
В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при <math>n=1</math> импликация <math>(\forall i\in\{1;\dots;n-1\})P_i\longrightarrow P_n</math> эквивалентна <math>P_1</math>. Принцип полной математической индукции является прямым применением более сильной трансфинитной индукции.
Принцип полной математической индукции также эквивалентен аксиоме индукции в аксиомах Пеано.
История
Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида[1]. Современное название метода было введено де Морганом в 1838 году.
Примеры
Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство
- <math>1 + q + q^2 +\cdots + q^n = \frac{1 - q^{n + 1}}{1 -q}.</math>
Доказательство. Индукция по n.
База, n = 1:
- <math>1 + q = \frac{(1 - q)(1 + q)}{1 - q}=\frac{1 - q^{1 + 1}}{1 - q}.</math>
Переход: предположим, что
- <math>1 + q + \cdots + q^n=\frac{1- q^{n + 1}}{1 - q},</math>
тогда
- <math>1+q+\cdots +q^n+q^{n+1}=\frac{1-q^{n+1}}{1-q}+q^{n+1}=</math>
- <math>=\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}</math>,
что и требовалось доказать.
Комментарий: истинность утверждения <math>P_n</math> в этом доказательстве — то же, что истинность равенства
- <math>1+q+\cdots +q^n=\frac{1-q^{n+1}}{1-q}.</math>
Вариации и обобщения
Примечания
- ↑ Nachum L. Rabinovih Раби Леви бен Гершом и происхождение метода математической индукции = Rabbi Levi ben Gershom and the origins of mathematical induction // Archive for History of Exact Sciences. — 1970. — Вып. 6. — С. 237-248.
Литература
- А. Шень. [math.ru/lib/430 Математическая индукция]. — МЦНМО, 2004. — 36 с.
- Н. Я. Виленкин. Индукция. Комбинаторика. — Пособие для учителей. — М.: Просвещение, 1976. — 48 с.
- Л. И. Головина, И. М. Яглом. [plm.mccme.ru/ann/a21.htm Индукция в геометрии]. — Физматгиз, 1961. — Т. 21. — 100 с. — (Популярные лекции по математике).
- Р. Курант, Г. Роббинс. Глава I, § 2 // [www.mccme.ru/free-books/pdf/kurant.htm Что такое математика?]
- И. С. Соминский. [plm.mccme.ru/ann/a03.htm Метод математической индукции]. — Наука, 1965. — Т. 3. — 58 с. — (Популярные лекции по математике).
Ссылки
- [www.youtube.com/watch?v=J0qEx8owPrQ Видео] по методу математической индукции