Просмотр кода страницы Математическая индукция

[[Файл:Dominoeffect.png|thumb|300px|Доказательство по индукции можно проиллюстрировать [[Принцип домино|принципом домино]]]]
'''Математическая индукция''' — метод [[Математическое доказательство|математического доказательства]], который используется, чтобы доказать истинность некоторого утверждения для всех [[натуральное число|натуральных чисел]]. Для этого сначала проверяется истинность утверждения с номером <math>1</math> — '''''база индукции''''', а затем доказывается, что если верно утверждение с номером <math>n</math>, то верно и следующее утверждение с номером <math>n+1</math> — '''''шаг индукции''''', или '''''индукционный переход'''''.

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

== Формулировка ==
Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных [[натуральное число|натуральными числами]]: <math>P_1, P_2, \ldots, P_n, P_{n+1}, \ldots</math>.

Допустим, что
# Установлено, что <math>P_1</math> верно. (Это утверждение называется ''базой индукции''.)
# Для любого <math>n</math> доказано, что если верно <math>P_n</math>, то верно <math>P_{n+1}</math>. (Это утверждение называется ''индукционным переходом''.)
Тогда все утверждения нашей последовательности верны.

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

== Принцип полной математической индукции ==
Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:
{{Рамка}}
Пусть имеется последовательность утверждений <math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>\ldots</math>. Если для натурального <math>n > 1</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}, n > 1)\Big((\forall i\in\{1;\dots;n-1\})P_i\Rightarrow P_n\Big)\Rightarrow(\forall n\in{\mathbb N})P_n</math>.
{{конец рамки}}
В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при <math>n=1</math> условие <math>(\forall i\in\{1;\dots;n-1\})P_i\Rightarrow P_n</math> в точности эквивалентно <math>P_1</math> (его истинности не из чего следовать). Однако зачастую доказывать индукционный переход для <math>P_1</math> всё равно приходится отдельно, так что разумно бывает выделить эту его часть в качестве базы.

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

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

== История ==
Отдельные случаи следов применения индукции встречаются ещё в античные времена у [[Прокл Диадох|Прокла]] и [[Евклид|Евклида]]<ref>{{cite journal|last=Acerbi|first=Fabio|date=Aug 2000|title=Plato: ''Parmenides'' 149a7-c3. A Proof by Complete Induction?|url=https://www.academia.edu/8016024|journal=[[Archive for History of Exact Sciences]]|volume=55|issue=1|pages=57–76|doi=10.1007/s004070000020|jstor=41134098|s2cid=123045154}}</ref>, однако они не предоставили никаких индуктивных доказательств, а довольствовались интуитивными, примерными индукциями, которые, однако, можно завершить<ref>Rabinovitch: ''Rabbi Levi Ben Gershon and the Origins of Mathematical Induction'', in: Archive for History of Exact Sciences 6 (1970), S. 237–248.</ref>.

Самое раннее неявное доказательство методом математической индукции было написано [[Абу Бакр аль-Караджи|аль-Караджи]] в около 1000 году, который применил его к [[Арифметическая прогрессия|арифметическим последовательностям]] для доказательства [[Бином Ньютона|бинома Ньютона]] и свойств [[Треугольник Паскаля|треугольника Паскаля]], открытых им задолго до европейских математиков. Хотя его оригинальная работа была утрачена, на неё позднее ссылался [[аль-Самуал]] в своем трактате «''аль-Бахир фи'ль-джабр''» (Сияние Алгебры) около 1150 года, который также неявно пользовался доказательством методом математической индукции<ref>{{cite book|last=Rashed|first=R.|title=The Development of Arabic Mathematics: Between Arithmetic and Algebra|url=https://books.google.com/books?id=vSkClSvU_9AC&pg=PA62|publisher=Springer Science & Business Media|year=1994|volume=156|isbn=9780792325659|language=en|series=Boston Studies in the Philosophy of Science|contribution=Mathematical induction: al-Karajī and al-Samawʾal}}</ref><ref>[https://books.google.com/books?id=HGMXCgAAQBAJ&pg=PA193 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"</ref>.
{{quote|текст=Еще одна важная идея, введенная аль-Караджи и продолженная аль-Самуалом и другими, заключалась в использовании индуктивного аргумента для работы с определенными арифметическими последовательностями. Так, аль-Караджи использовал такой аргумент для доказательства формулы суммы целых кубов, которая уже была известна [[Ариабхата|Ариабхате]] <...> Однако аль-Караджи не утверждал общий результат для произвольного n. Он заявил свою теорему для конкретного числа 10 <...> Его доказательство, тем не менее, явно предназначалось для распространения на любое другое целое число. <...> Аргумент аль-Караджи по существу включает два основных компонента современного доказательства методом индукции, а именно истинность утверждения для <math>n=1</math> <math>(1=1^3)</math> и вывод истинности для <math>n=k</math> из истинности для <math>n=k-1</math>. Конечно, этот второй компонент не является явным, так как в некотором смысле аргумент аль-Караджи идет в обратном порядке; то есть он начинает с <math>n=10</math> и идет вниз до 1, а не поднимается вверх. Тем не менее, его аргумент в ''аль-Фахри'' является самым ранним сохранившимся доказательством формулы суммы целых кубов.|автор=[[Виктор Кац]]|источник=История Математики: Введение<ref>{{cite book|last=Katz|first=Victor J.|author-link=Victor J. Katz|year=1998|title=History of Mathematics: An Introduction |url=https://archive.org/details/historyofmathema00katz| publisher=[[Addison-Wesley]]|isbn=0-321-01618-1}}</ref>}}
Самое раннее строгое использование индукции принадлежит [[Герсонид|Герсониду]] (1288–1344)<ref>{{cite journal|last=Simonson|first=Charles G.|date=Winter 2000|title=The Mathematics of Levi ben Gershon, the Ralbag|url=http://web.stonehill.edu/compsci/Shai_papers/MathofLevi.pdf|journal=Bekhol Derakhekha Daehu|publisher=Bar-Ilan University Press|volume=10|pages=5–21}}</ref><ref>{{cite journal|last=Rabinovitch|first=Nachum L.|author-link=Nahum Rabinovitch|year=1970|title=Rabbi Levi Ben Gershon and the origins of mathematical induction|journal=Archive for History of Exact Sciences|volume=6|issue=3|pages=237–248|doi=10.1007/BF00327237|mr=1554128|s2cid=119948133}}</ref>, а первая явная формулировка принципа математической индукции была дана [[Блез Паскаль|Паскалем]] в его ''Traité du triangle arithmétique'' (1665). Другой француз, [[Пьер Ферма|Ферма]], активно использовал связанный с индукцией принцип: косвенное доказательство [[Метод бесконечного спуска|методом бесконечного спуска]].

Гипотеза индукции также использовалась швейцарцем [[Якоб Бернулли|Якобом Бернулли]], после чего этот метод стал широко известен. Современное формальное изложение принципа появилось только в XIX веке с работами [[Буль, Джордж|Джорджа Буля]]<ref>«Иногда требуется доказать теорему, которая будет верна всякий раз, когда величина ''n'', включенная в неё, является целым числом, и метод доказательства обычно следующий. ''Во-первых'', теорема доказывается для {{nowrap|1=''n'' = 1}}. ''Во-вторых'', доказывается, что если теорема верна для данного целого числа ''n'', то она будет верна и для следующего целого числа ''n''+1. Следовательно, теорема верна в общем случае.» (Буль, около 1849, ''Элементарный трактат о логике, не математический'', стр. 40–41, переиздано в Граттан-Гиннесс, Айвор и Борне, Жерар (1997), ''Джордж Буль: Избранные рукописи по логике и её философии'', Birkhäuser Verlag, Берлин, {{isbn|3-7643-5456-9}})</ref>, [[Огастес де Морган|Огастеса де Моргана]], [[Чарльз Сандерс Пирс|Чарльза Сандерса Пирса]]<ref>{{cite book|last=Shields|first=Paul|chapter=Peirce's Axiomatization of Arithmetic|title=Studies in the Logic of Charles S. Peirce|url=https://archive.org/details/studiesinlogicof00nath|publisher=Indiana University Press|year=1997|pages=43–52|isbn=0-253-33020-3|url-access=registration|mr=1720827|editor1-first=Nathan|editor1-last=Houser|editor2-first=Don D.|editor2-last=Roberts|editor3-first=James Van|editor3-last=Evra}}</ref>, [[Джузеппе Пеано]] и [[Рихард Дедекинд|Рихарда Дедекинда]]<ref>{{cite journal|last=Bussey|first=W. H.|year=1917|title=The Origin of Mathematical Induction|journal=[[The American Mathematical Monthly]]|volume=24|issue=5|pages=199–207|doi=10.2307/2974308|jstor=2974308}}</ref>.

== Примеры ==
'''Сумма геометрической прогрессии.''' Доказать, что, каковы бы ни были натуральное <math>n</math> и вещественное <math>q\ne 1</math>, выполняется равенство
: <math>\sum_{i=0}^{n}q^i\equiv 1 + q + q^2 +\cdots + q^n = \frac{1 - q^{n + 1}}{1  -q}.</math>

'''Доказательство.''' Индукцией по <math>n</math> для произвольного <math>q</math>.

Докажем ''базу индукции'' для ''<math>n=1</math>'':
: <math>1 + q = \frac{(1 - q)(1 + q)}{1 - q}=\frac{1 - q^{1 + 1}}{1 - q}.</math>
Докажем ''переход'': предположим, что для <math>n=k</math> выполнено
: <math>1 + q + \cdots + q^k=\frac{1- q^{k + 1}}{1 - q},</math>
тогда для <math>n=k+1</math>, согласно предположению:
: <math>1+q+\cdots +q^k+q^{k+1}=\frac{1-q^{k+1}}{1-q}+q^{k+1}=</math>
: <math>=\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>n</math>. Что и требовалось доказать.

'''Комментарий:''' истинность утверждения <math>P_n</math> в этом доказательстве — то же, что истинность равенства
: <math>1+q+\cdots +q^n=\frac{1-q^{n+1}}{1-q}.</math>
'''Важные примеры:''' [[ряд из натуральных чисел]], [[неравенство Бернулли]], [[бином Ньютона]].

== Вариации и обобщения ==
* [[Обратная индукция]]
* [[Структурная индукция]]
* [[Трансфинитная индукция]]

== См. также ==
* [[Математический софизм#Доказательство по индукции|Математический софизм в доказательствах по индукции]]
** [[Доказательство одноцветности всех лошадей]]

== Примечания ==
{{примечания}}

== Литература ==
{{викиучебник|Знакомство с методом математической индукции}}
* {{книга |автор=А. Шень |заглавие=Математическая индукция |издательство=[[МЦНМО]] |год=2004 |страниц=36 |ссылка=http://math.ru/lib/430}}
* {{книга |автор=[[Виленкин, Наум Яковлевич|Н. Я. Виленкин]] |заглавие=Индукция. Комбинаторика |издание=Пособие для учителей |место=М. |издательство=Просвещение |год=1976 |страниц=48}}
* {{книга |автор=Л. И. Головина, [[Яглом, Исаак Моисеевич|И. М. Яглом]] |заглавие=Индукция в геометрии |серия=[[Популярные лекции по математике]] |том=21 |издательство=[[Физматгиз]] |год=1961 |страниц=100 |ссылка=http://plm.mccme.ru/ann/a21.htm}}
* {{книга |автор=[[Курант, Рихард|Р. Курант]], Г. Роббинс |заглавие=Что такое математика? |nodot=1 |часть=Глава I, §&nbsp;2 |ссылка=http://www.mccme.ru/free-books/pdf/kurant.htm}}
* {{книга |автор=И. С. Соминский |заглавие=Метод математической индукции |серия=[[Популярные лекции по математике]] |том=3 |издательство=Наука |год=1965 |страниц=58 |ссылка=http://plm.mccme.ru/ann/a03.htm}}

== Ссылки ==
* [https://www.youtube.com/watch?v=J0qEx8owPrQ Видео] по методу математической индукции
{{вс}}

[[Категория:Математическая индукция и её обобщения]]
[[Категория:Рекурсия]]
[[Категория:Практики, основанные на доказательствах]]