WikiSort.ru - Не сортированное

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

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

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

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

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

История

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

Примеры

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

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

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

База, n = 1:

${\displaystyle 1+q={\frac {(1-q)(1+q)}{1-q}}={\frac {1-q^{1+1}}{1-q}}.}$

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

${\displaystyle 1+q+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}},}$

тогда

${\displaystyle 1+q+\cdots +q^{n}+q^{n+1}={\frac {1-q^{n+1}}{1-q}}+q^{n+1}=}$

${\displaystyle ={\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}}}$ ,

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

Комментарий: истинность утверждения ${\displaystyle P_{n}}$ в этом доказательстве — то же, что истинность равенства

${\displaystyle 1+q+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}$

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

• Трансфинитная индукция
• Структурная индукция
• Аксиомы Пеано
• Обратная индукция или Индукция Коши
• Доказательство одноцветности всех лошадей

Примечания

Литература

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

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

Ссылки

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