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

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

Доказательство по индукции можно проиллюстрировать принципом домино

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

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

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

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

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

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

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

Принцип полной математической индукции

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

Пусть имеется последовательность утверждений ${\displaystyle P_{1}}$, ${\displaystyle P_{2}}$, ${\displaystyle P_{3}}$, ${\displaystyle \ldots }$. Если для натурального ${\displaystyle n>1}$ из того, что истинны все ${\displaystyle P_{1}}$, ${\displaystyle P_{2}}$, ${\displaystyle P_{3}}$, ${\displaystyle \ldots }$, ${\displaystyle P_{n-1}}$, следует также истинность ${\displaystyle P_{n}}$, то все утверждения в этой последовательности истинны, то есть ${\displaystyle (\forall n\in {\mathbb {N} },n>1){\Big (}(\forall i\in \{1;\dots ;n-1\})P_{i}\Rightarrow P_{n}{\Big )}\Rightarrow (\forall n\in {\mathbb {N} })P_{n}}$.

В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при ${\displaystyle n=1}$ условие ${\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\Rightarrow P_{n}}$ в точности эквивалентно ${\displaystyle P_{1}}$ (его истинности не из чего следовать). Однако зачастую доказывать индукционный переход для ${\displaystyle P_{1}}$ всё равно приходится отдельно, так что разумно бывает выделить эту его часть в качестве базы.

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

Также он является прямым применением более сильной трансфинитной индукции.

История

Отдельные случаи следов применения индукции встречаются ещё в античные времена у Прокла и Евклида^[1], однако они не предоставили никаких индуктивных доказательств, а довольствовались интуитивными, примерными индукциями, которые, однако, можно завершить^[2].

Самое раннее неявное доказательство методом математической индукции было написано аль-Караджи в около 1000 году, который применил его к арифметическим последовательностям для доказательства бинома Ньютона и свойств треугольника Паскаля, открытых им задолго до европейских математиков. Хотя его оригинальная работа была утрачена, на неё позднее ссылался аль-Самуал в своем трактате «аль-Бахир фи'ль-джабр» (Сияние Алгебры) около 1150 года, который также неявно пользовался доказательством методом математической индукции^[3][4].

Еще одна важная идея, введенная аль-Караджи и продолженная аль-Самуалом и другими, заключалась в использовании индуктивного аргумента для работы с определенными арифметическими последовательностями. Так, аль-Караджи использовал такой аргумент для доказательства формулы суммы целых кубов, которая уже была известна Ариабхате <...> Однако аль-Караджи не утверждал общий результат для произвольного n. Он заявил свою теорему для конкретного числа 10 <...> Его доказательство, тем не менее, явно предназначалось для распространения на любое другое целое число. <...> Аргумент аль-Караджи по существу включает два основных компонента современного доказательства методом индукции, а именно истинность утверждения для ${\displaystyle n=1}$ ${\displaystyle (1=1^{3})}$ и вывод истинности для ${\displaystyle n=k}$ из истинности для ${\displaystyle n=k-1}$. Конечно, этот второй компонент не является явным, так как в некотором смысле аргумент аль-Караджи идет в обратном порядке; то есть он начинает с ${\displaystyle n=10}$ и идет вниз до 1, а не поднимается вверх. Тем не менее, его аргумент в аль-Фахри является самым ранним сохранившимся доказательством формулы суммы целых кубов.Виктор Кац, История Математики: Введение^[5]

Самое раннее строгое использование индукции принадлежит Герсониду (1288–1344)^[6][7], а первая явная формулировка принципа математической индукции была дана Паскалем в его Traité du triangle arithmétique (1665). Другой француз, Ферма, активно использовал связанный с индукцией принцип: косвенное доказательство методом бесконечного спуска.

Гипотеза индукции также использовалась швейцарцем Якобом Бернулли, после чего этот метод стал широко известен. Современное формальное изложение принципа появилось только в XIX веке с работами Джорджа Буля^[8], Огастеса де Моргана, Чарльза Сандерса Пирса^[9], Джузеппе Пеано и Рихарда Дедекинда^[10].

Примеры

Сумма геометрической прогрессии. Доказать, что, каковы бы ни были натуральное ${\displaystyle n}$ и вещественное ${\displaystyle q\neq 1}$, выполняется равенство

${\displaystyle \sum _{i=0}^{n}q^{i}\equiv 1+q+q^{2}+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}$

Доказательство. Индукцией по ${\displaystyle n}$ для произвольного ${\displaystyle q}$.

Докажем базу индукции для ${\displaystyle n=1}$:

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

Докажем переход: предположим, что для ${\displaystyle n=k}$ выполнено

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

тогда для ${\displaystyle n=k+1}$, согласно предположению:

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

${\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}}}$.

Значит по принципу математической индукции выполнено равенство для всякого ${\displaystyle n}$. Что и требовалось доказать.

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

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

Важные примеры: ряд из натуральных чисел, неравенство Бернулли, бином Ньютона.

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

• Обратная индукция
• Структурная индукция
• Трансфинитная индукция

См. также

• Математический софизм в доказательствах по индукции
  • Доказательство одноцветности всех лошадей

Примечания

1. Acerbi, Fabio (Aug 2000). "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences. 55 (1): 57—76. doi:10.1007/s004070000020. JSTOR 41134098. S2CID 123045154.
2. Rabinovitch: Rabbi Levi Ben Gershon and the Origins of Mathematical Induction, in: Archive for History of Exact Sciences 6 (1970), S. 237–248.
3. Rashed, R. The Development of Arabic Mathematics: Between Arithmetic and Algebra : [англ.]. — Springer Science & Business Media, 1994. — Vol. 156. — ISBN 9780792325659.
4. Mathematical Knowledge and the Interplay of Practices "The earliest implicit proof by mathematical induction was given around 1000 in a work by the Persian mathematician Al-Karaji"
5. Katz, Victor J. History of Mathematics: An Introduction. — Addison-Wesley, 1998. — ISBN 0-321-01618-1.
6. Simonson, Charles G. (Winter 2000). "The Mathematics of Levi ben Gershon, the Ralbag" (PDF). Bekhol Derakhekha Daehu. 10. Bar-Ilan University Press: 5—21.
7. Rabinovitch, Nachum L. (1970). "Rabbi Levi Ben Gershon and the origins of mathematical induction". Archive for History of Exact Sciences. 6 (3): 237—248. doi:10.1007/BF00327237. MR 1554128. S2CID 119948133.
8. «Иногда требуется доказать теорему, которая будет верна всякий раз, когда величина n, включенная в неё, является целым числом, и метод доказательства обычно следующий. Во-первых, теорема доказывается для n = 1. Во-вторых, доказывается, что если теорема верна для данного целого числа n, то она будет верна и для следующего целого числа n+1. Следовательно, теорема верна в общем случае.» (Буль, около 1849, Элементарный трактат о логике, не математический, стр. 40–41, переиздано в Граттан-Гиннесс, Айвор и Борне, Жерар (1997), Джордж Буль: Избранные рукописи по логике и её философии, Birkhäuser Verlag, Берлин, ISBN 3-7643-5456-9)
9. Shields, Paul. Peirce's Axiomatization of Arithmetic // Studies in the Logic of Charles S. Peirce. — Indiana University Press, 1997. — P. 43–52. — ISBN 0-253-33020-3.
10. Bussey, W. H. (1917). "The Origin of Mathematical Induction". The American Mathematical Monthly. 24 (5): 199—207. doi:10.2307/2974308. JSTOR 2974308.

Литература

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

Ссылки

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