Математическая индукция
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером [math]\displaystyle{ 1 }[/math] — база (базис) индукции, а затем доказывается, что если верно утверждение с номером [math]\displaystyle{ n }[/math], то верно и следующее утверждение с номером [math]\displaystyle{ n+1 }[/math] — шаг индукции, или индукционный переход.
Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино. Пусть какое угодно число косточек домино выставлено в ряд таким образом, что каждая косточка, падая, обязательно опрокидывает следующую за ней косточку (в этом заключается индукционный переход). Тогда, если мы толкнём первую косточку (это база индукции), то все косточки в ряду упадут.
Формулировка
Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: [math]\displaystyle{ P_1, P_2, \ldots, P_n, P_{n+1}, \ldots }[/math].
Допустим, что
- Установлено, что [math]\displaystyle{ P_1 }[/math] верно. (Это утверждение называется базой индукции.)
- Для любого [math]\displaystyle{ n }[/math] доказано, что если верно [math]\displaystyle{ P_n }[/math], то верно [math]\displaystyle{ P_{n+1} }[/math]. (Это утверждение называется индукционным переходом.)
Тогда все утверждения нашей последовательности верны.
Логическим основанием для этого метода доказательства служит так называемая аксиома индукции, пятая из аксиом Пеано, определяющих натуральные числа. Верность метода индукции эквивалентна тому, что в любом непустом подмножестве натуральных чисел существует минимальный элемент.
Первый принцип математической индукции
Для предиката [math]\displaystyle{ P(n) }[/math], определенного на множестве неотрицательных целых чисел [math]\displaystyle{ \mathbb{N}=\{0,1,2,\ldots\} }[/math], если
| 1. | [math]\displaystyle{ P(0) }[/math], и | базис индукции |
| 1. | [math]\displaystyle{ P(n) \rightarrow P(n+1) }[/math] | индукционный шаг |
то [math]\displaystyle{ \forall nP(n) }[/math].
[math]\displaystyle{ P(n) }[/math] называется индукционным предикатом или индукционным предложением, [math]\displaystyle{ n }[/math] - индукционной переменной, первое условие - базисом индукции, второе условие - индукционным шагом.
Логическим основанием для первого принципа математической индукции служит так называемая аксиома индукции, пятая из аксиом Пеано, определяющих натуральные числа. Верность метода индукции эквивалентна тому, что в любом непустом подмножестве натуральных чисел существует минимальный элемент.
Аксиома индукции
Если [math]\displaystyle{ S }[/math] - множество натуральных чисел такое, что
- 1. [math]\displaystyle{ 0\in S }[/math],
- 2. если [math]\displaystyle{ n\in S }[/math], то [math]\displaystyle{ n+1\in S }[/math], то
- [math]\displaystyle{ S=\mathbb{N} }[/math]
Применяя аксиому индукции к множеству истинности предиката [math]\displaystyle{ P(n) }[/math] мы получаем формулировку первого принципа математической индукции.
Принцип полной математической индукции. Второй принцип математической индукции
Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:
|
Пусть имеется последовательность утверждений [math]\displaystyle{ P_1 }[/math], [math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ \ldots }[/math]. Если для любого натурального [math]\displaystyle{ n }[/math] из того, что истинны все [math]\displaystyle{ P_1 }[/math], [math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ P_3 }[/math], [math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ P_{n-1} }[/math], следует также истинность [math]\displaystyle{ P_n }[/math], то все утверждения в этой последовательности истинны, то есть [math]\displaystyle{ (\forall n\in{\mathbb N})\Big((\forall i\in\{1;\dots;n-1\})P_i\Rightarrow P_n\Big)\Rightarrow(\forall n\in{\mathbb N})P_n }[/math]. |
В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при [math]\displaystyle{ n=1 }[/math] условие [math]\displaystyle{ (\forall i\in\{1;\dots;n-1\})P_i\Rightarrow P_n }[/math] в точности эквивалентно [math]\displaystyle{ P_1 }[/math] (его истинности не из чего следовать). Однако зачастую доказывать индукционный переход для [math]\displaystyle{ P_1 }[/math] всё равно приходится отдельно, так что разумно бывает выделить эту его часть в качестве базы.
Поэтому полную математическую индукцию можно сформулировать таким образом:
- 1. [math]\displaystyle{ P(k) }[/math], и
- 2. из [math]\displaystyle{ P(j) }[/math] верного для [math]\displaystyle{ k \le j \le n }[/math] следует [math]\displaystyle{ P(n+1) }[/math]
- то [math]\displaystyle{ \forall nP(n) }[/math].
Принцип полной математической индукции используется в информатике, например, для доказательства рекуррентных формул и для определения числа операций в процедурах информатики "разделяй и властвуй".
Принцип полной математической индукции эквивалентен аксиоме индукции в аксиомах Пеано.
Также он является прямым применением более сильной трансфинитной индукции.
История
История разработки метода математической индукции восходит к Франческо Мавролико, Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида[1]. Мавролико в явной форме сформулировал метод математической индукции для доказательства [math]\displaystyle{ 1 + 3 + 5 + \cdots + (2n - 1) = n^2 }[/math]. Паскаль использовал математическую индукцию для формулировки треугольника Паскаля - бесконечной таблицы биномиальных коэффициентов.[2] Современное название метода было введено де Морганом в 1838 году.
Примеры
Сумма геометрической прогрессии. Доказать, что, каковы бы ни были натуральное [math]\displaystyle{ n }[/math] и вещественное [math]\displaystyle{ q\ne 1 }[/math], выполняется равенство
- [math]\displaystyle{ \sum_{i=0}^{n}q^i\equiv 1 + q + q^2 +\cdots + q^n = \frac{1 - q^{n + 1}}{1 -q}. }[/math]
Доказательство. Индукцией по [math]\displaystyle{ n }[/math] для произвольного [math]\displaystyle{ q }[/math].
Докажем базу индукции для [math]\displaystyle{ n=1 }[/math]:
- [math]\displaystyle{ 1 + q = \frac{(1 - q)(1 + q)}{1 - q}=\frac{1 - q^{1 + 1}}{1 - q}. }[/math]
Докажем переход: предположим, что для [math]\displaystyle{ n=k }[/math] выполнено
- [math]\displaystyle{ 1 + q + \cdots + q^k=\frac{1- q^{k + 1}}{1 - q}, }[/math]
тогда для [math]\displaystyle{ n=k+1 }[/math], согласно предположению:
- [math]\displaystyle{ 1+q+\cdots +q^k+q^{k+1}=\frac{1-q^{k+1}}{1-q}+q^{k+1}= }[/math]
- [math]\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} }[/math].
Значит по принципу математической индукции выполнено равенство для всякого [math]\displaystyle{ n }[/math]. Что и требовалось доказать.
Комментарий: истинность утверждения [math]\displaystyle{ P_n }[/math] в этом доказательстве — то же, что истинность равенства
- [math]\displaystyle{ 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.
- ↑ Contemporary Joseph A. Gallian Abstract Algebra, Ninth Edition 2017, 2013 Cengage Learning
Литература
- А. Шень. Математическая индукция. — МЦНМО, 2004. — 36 с.
- Н. Я. Виленкин. Индукция. Комбинаторика. — Пособие для учителей. — М.: Просвещение, 1976. — 48 с.
- Л. И. Головина, И. М. Яглом. Индукция в геометрии. — Физматгиз, 1961. — Т. 21. — 100 с. — (Популярные лекции по математике).
- Р. Курант, Г. Роббинс. Глава I, § 2 // Что такое математика?
- И. С. Соминский. Метод математической индукции. — Наука, 1965. — Т. 3. — 58 с. — (Популярные лекции по математике).
Ссылки
- Видео по методу математической индукции