Википедия

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

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

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

Содержание

1 Формулировка
- 1.1 Принцип полной математической индукции
2 История
3 Примеры
4 Вариации и обобщения
5 Примечания
6 Литература
7 Ссылки

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

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

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

Установлено, что $P_1$ верно. (Это утверждение называется базой индукции.)
Для любого 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}.$

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

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

Примечания

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

Литература

Имеется викиучебник по теме
«Математическая индукция»

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

Ссылки

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

Категория:

Математическая логика

Wikimedia Foundation. 2010.

См. также в других словарях:

МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — полная математическая индукция (наз. в математике часто просто полной индукцией; в этом случае это понятие следует отличать от рассматриваемого в нематематич. формальной логике понятия полной индукции), – прием доказательства общих предложений в… … Философская энциклопедия
МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ, метод, доказывающий, что математическое утверждение верно для любого положительного целого числа п, если выполняются два условия: 1) оно верно для основной величины, например, 1, и 2) если оно верно для значения k, то… … Научно-технический энциклопедический словарь
МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — МАТЕМАТИЧЕСКАЯ индукция, способ доказательства или определения некоторого свойства A для всех n случаев, основанный на переходе заключения о наличии свойства A от n к n+1. Математическая индукция состоит из двух этапов: установление A для… … Современная энциклопедия
МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — общий способ математического доказательства или определения некоторого свойства А для всех натуральных n, основанный на заключении от n к n+1. Математическая индукция состоит из двух этапов: а) установление А для некоторого начального n0; б)… … Большой Энциклопедический словарь
математическая индукция — общий способ математического доказательства или определения некоторого свойства А для всех натуральных n, основанный на заключении от n к n + 1, математическая индукция состоит из двух этапов: а) установление А для некоторого начального n0;… … Энциклопедический словарь

МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — метод доказательства математич. утверждений, основанный на принципе математической индукции: утверждение (х), зависящее от натурального параметра х, считается доказанным, если доказано А(1) и для любого натурального пиз предположения, что верно… … Математическая энциклопедия
Индукция Математическая, Полная Математическая Индукция — а средство доказательства общих положений в матемантике и др. дедуктивных науках. Этот прием опирается на использованние двух… … Словарь терминов логики
математическая индукция — mathematical induction … Большой англо-русский и русско-английский словарь
Математическая индукция — весьма общий способ математических доказательств и определений. Индуктивные доказательства основаны на так называемом принципе М. и., являющемся одной из основных математических аксиом. Пусть, например, требуется доказать для любого… … Большая советская энциклопедия
математическая индукция — math(ematical) induction, induction … Англо-русский словарь технических терминов

Книги

Дискретная математика для программистов (+ CD-ROM), Г. Хаггард, Дж. Шлипф, С. Уайтсайдс Подробнее Купить за 632 руб
Начала теории множеств. Математическая логика и теория алгоритмов., Н. К. Верещагин, А. Шень Подробнее Купить за 161 руб
Математическая индукция, А. Шень Подробнее Купить за 54 руб

Словари и энциклопедии на Академике