Математическая индукция
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
Доказательство по индукции наглядно может быть представлено в виде так называемого принципа домино. Пусть какое угодно число косточек домино выставлено в ряд таким образом, что каждая косточка, падая, обязательно опрокидывает следующую за ней косточку (в этом заключается индукционный переход). Тогда, если мы толкнём первую косточку (это база индукции), то все косточки в ряду упадут.
Содержание
Формулировка
Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: <math>P_1, P_2, \ldots, P_n, P_{n+1}, \ldots</math>.
Допустим, что
Тогда все утверждения нашей последовательности верны. |
Логическим основанием для этого метода доказательства служит так называемая аксиома индукции, пятая из аксиом Пеано, определяющих натуральные числа. Верность метода индукции эквивалентна тому, что в любом непустом подмножестве натуральных чисел существует минимальный элемент.
Принцип полной математической индукции
Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:
Пусть имеется последовательность утверждений <math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>\ldots</math>. Если для любого натурального <math>n</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})\Big((\forall i\in\{1;\dots;n-1\})P_i\longrightarrow P_n\Big)\longrightarrow(\forall n\in{\mathbb N})P_n</math>. |
В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при <math>n=1</math> импликация <math>(\forall i\in\{1;\dots;n-1\})P_i\longrightarrow P_n</math> эквивалентна <math>P_1</math>. Принцип полной математической индукции является прямым применением более сильной трансфинитной индукции.
Принцип полной математической индукции также эквивалентен аксиоме индукции в аксиомах Пеано.
История
Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида[1]. Современное название метода было введено де Морганом в 1838 году.
Примеры
Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство
- <math>1 + q + q^2 +\cdots + q^n = \frac{1 - q^{n + 1}}{1 -q}.</math>
Доказательство. Индукция по n.
База, n = 1:
- <math>1 + q = \frac{(1 - q)(1 + q)}{1 - q}=\frac{1 - q^{1 + 1}}{1 - q}.</math>
Переход: предположим, что
- <math>1 + q + \cdots + q^n=\frac{1- q^{n + 1}}{1 - q},</math>
тогда
- <math>1+q+\cdots +q^n+q^{n+1}=\frac{1-q^{n+1}}{1-q}+q^{n+1}=</math>
- <math>=\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}</math>,
что и требовалось доказать.
Комментарий: истинность утверждения <math>P_n</math> в этом доказательстве — то же, что истинность равенства
- <math>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.
Литература
- А. Шень. [math.ru/lib/430 Математическая индукция]. — МЦНМО, 2004. — 36 с.
- Н. Я. Виленкин. Индукция. Комбинаторика. — Пособие для учителей. — М.: Просвещение, 1976. — 48 с.
- Л. И. Головина, И. М. Яглом. [plm.mccme.ru/ann/a21.htm Индукция в геометрии]. — Физматгиз, 1961. — Т. 21. — 100 с. — (Популярные лекции по математике).
- Р. Курант, Г. Роббинс. Глава I, § 2 // [www.mccme.ru/free-books/pdf/kurant.htm Что такое математика?]
- И. С. Соминский. [plm.mccme.ru/ann/a03.htm Метод математической индукции]. — Наука, 1965. — Т. 3. — 58 с. — (Популярные лекции по математике).
Ссылки
- [www.youtube.com/watch?v=J0qEx8owPrQ Видео] по методу математической индукции
Отрывок, характеризующий Математическая индукция
Остатки войск Ланжерона и Дохтурова, смешавшись, теснились около прудов на плотинах и берегах у деревни Аугеста.В 6 м часу только у плотины Аугеста еще слышалась жаркая канонада одних французов, выстроивших многочисленные батареи на спуске Праценских высот и бивших по нашим отступающим войскам.
В арьергарде Дохтуров и другие, собирая батальоны, отстреливались от французской кавалерии, преследовавшей наших. Начинало смеркаться. На узкой плотине Аугеста, на которой столько лет мирно сиживал в колпаке старичок мельник с удочками, в то время как внук его, засучив рукава рубашки, перебирал в лейке серебряную трепещущую рыбу; на этой плотине, по которой столько лет мирно проезжали на своих парных возах, нагруженных пшеницей, в мохнатых шапках и синих куртках моравы и, запыленные мукой, с белыми возами уезжали по той же плотине, – на этой узкой плотине теперь между фурами и пушками, под лошадьми и между колес толпились обезображенные страхом смерти люди, давя друг друга, умирая, шагая через умирающих и убивая друг друга для того только, чтобы, пройдя несколько шагов, быть точно. так же убитыми.
Каждые десять секунд, нагнетая воздух, шлепало ядро или разрывалась граната в средине этой густой толпы, убивая и обрызгивая кровью тех, которые стояли близко. Долохов, раненый в руку, пешком с десятком солдат своей роты (он был уже офицер) и его полковой командир, верхом, представляли из себя остатки всего полка. Влекомые толпой, они втеснились во вход к плотине и, сжатые со всех сторон, остановились, потому что впереди упала лошадь под пушкой, и толпа вытаскивала ее. Одно ядро убило кого то сзади их, другое ударилось впереди и забрызгало кровью Долохова. Толпа отчаянно надвинулась, сжалась, тронулась несколько шагов и опять остановилась.
Пройти эти сто шагов, и, наверное, спасен; простоять еще две минуты, и погиб, наверное, думал каждый. Долохов, стоявший в середине толпы, рванулся к краю плотины, сбив с ног двух солдат, и сбежал на скользкий лед, покрывший пруд.
– Сворачивай, – закричал он, подпрыгивая по льду, который трещал под ним, – сворачивай! – кричал он на орудие. – Держит!…
Лед держал его, но гнулся и трещал, и очевидно было, что не только под орудием или толпой народа, но под ним одним он сейчас рухнется. На него смотрели и жались к берегу, не решаясь еще ступить на лед. Командир полка, стоявший верхом у въезда, поднял руку и раскрыл рот, обращаясь к Долохову. Вдруг одно из ядер так низко засвистело над толпой, что все нагнулись. Что то шлепнулось в мокрое, и генерал упал с лошадью в лужу крови. Никто не взглянул на генерала, не подумал поднять его.
– Пошел на лед! пошел по льду! Пошел! вороти! аль не слышишь! Пошел! – вдруг после ядра, попавшего в генерала, послышались бесчисленные голоса, сами не зная, что и зачем кричавшие.
Одно из задних орудий, вступавшее на плотину, своротило на лед. Толпы солдат с плотины стали сбегать на замерзший пруд. Под одним из передних солдат треснул лед, и одна нога ушла в воду; он хотел оправиться и провалился по пояс.
Ближайшие солдаты замялись, орудийный ездовой остановил свою лошадь, но сзади всё еще слышались крики: «Пошел на лед, что стал, пошел! пошел!» И крики ужаса послышались в толпе. Солдаты, окружавшие орудие, махали на лошадей и били их, чтобы они сворачивали и подвигались. Лошади тронулись с берега. Лед, державший пеших, рухнулся огромным куском, и человек сорок, бывших на льду, бросились кто вперед, кто назад, потопляя один другого.
Ядра всё так же равномерно свистели и шлепались на лед, в воду и чаще всего в толпу, покрывавшую плотину, пруды и берег.
На Праценской горе, на том самом месте, где он упал с древком знамени в руках, лежал князь Андрей Болконский, истекая кровью, и, сам не зная того, стонал тихим, жалостным и детским стоном.
К вечеру он перестал стонать и совершенно затих. Он не знал, как долго продолжалось его забытье. Вдруг он опять чувствовал себя живым и страдающим от жгучей и разрывающей что то боли в голове.
«Где оно, это высокое небо, которое я не знал до сих пор и увидал нынче?» было первою его мыслью. «И страдания этого я не знал также, – подумал он. – Да, я ничего, ничего не знал до сих пор. Но где я?»
Он стал прислушиваться и услыхал звуки приближающегося топота лошадей и звуки голосов, говоривших по французски. Он раскрыл глаза. Над ним было опять всё то же высокое небо с еще выше поднявшимися плывущими облаками, сквозь которые виднелась синеющая бесконечность. Он не поворачивал головы и не видал тех, которые, судя по звуку копыт и голосов, подъехали к нему и остановились.
Подъехавшие верховые были Наполеон, сопутствуемый двумя адъютантами. Бонапарте, объезжая поле сражения, отдавал последние приказания об усилении батарей стреляющих по плотине Аугеста и рассматривал убитых и раненых, оставшихся на поле сражения.