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

Поделись знанием:
Перейти к: навигация, поиск

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

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





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

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

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

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

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

Напишите отзыв о статье "Математическая индукция"

Примечания

  1. 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 м часу только у плотины Аугеста еще слышалась жаркая канонада одних французов, выстроивших многочисленные батареи на спуске Праценских высот и бивших по нашим отступающим войскам.
В арьергарде Дохтуров и другие, собирая батальоны, отстреливались от французской кавалерии, преследовавшей наших. Начинало смеркаться. На узкой плотине Аугеста, на которой столько лет мирно сиживал в колпаке старичок мельник с удочками, в то время как внук его, засучив рукава рубашки, перебирал в лейке серебряную трепещущую рыбу; на этой плотине, по которой столько лет мирно проезжали на своих парных возах, нагруженных пшеницей, в мохнатых шапках и синих куртках моравы и, запыленные мукой, с белыми возами уезжали по той же плотине, – на этой узкой плотине теперь между фурами и пушками, под лошадьми и между колес толпились обезображенные страхом смерти люди, давя друг друга, умирая, шагая через умирающих и убивая друг друга для того только, чтобы, пройдя несколько шагов, быть точно. так же убитыми.
Каждые десять секунд, нагнетая воздух, шлепало ядро или разрывалась граната в средине этой густой толпы, убивая и обрызгивая кровью тех, которые стояли близко. Долохов, раненый в руку, пешком с десятком солдат своей роты (он был уже офицер) и его полковой командир, верхом, представляли из себя остатки всего полка. Влекомые толпой, они втеснились во вход к плотине и, сжатые со всех сторон, остановились, потому что впереди упала лошадь под пушкой, и толпа вытаскивала ее. Одно ядро убило кого то сзади их, другое ударилось впереди и забрызгало кровью Долохова. Толпа отчаянно надвинулась, сжалась, тронулась несколько шагов и опять остановилась.
Пройти эти сто шагов, и, наверное, спасен; простоять еще две минуты, и погиб, наверное, думал каждый. Долохов, стоявший в середине толпы, рванулся к краю плотины, сбив с ног двух солдат, и сбежал на скользкий лед, покрывший пруд.
– Сворачивай, – закричал он, подпрыгивая по льду, который трещал под ним, – сворачивай! – кричал он на орудие. – Держит!…
Лед держал его, но гнулся и трещал, и очевидно было, что не только под орудием или толпой народа, но под ним одним он сейчас рухнется. На него смотрели и жались к берегу, не решаясь еще ступить на лед. Командир полка, стоявший верхом у въезда, поднял руку и раскрыл рот, обращаясь к Долохову. Вдруг одно из ядер так низко засвистело над толпой, что все нагнулись. Что то шлепнулось в мокрое, и генерал упал с лошадью в лужу крови. Никто не взглянул на генерала, не подумал поднять его.
– Пошел на лед! пошел по льду! Пошел! вороти! аль не слышишь! Пошел! – вдруг после ядра, попавшего в генерала, послышались бесчисленные голоса, сами не зная, что и зачем кричавшие.
Одно из задних орудий, вступавшее на плотину, своротило на лед. Толпы солдат с плотины стали сбегать на замерзший пруд. Под одним из передних солдат треснул лед, и одна нога ушла в воду; он хотел оправиться и провалился по пояс.
Ближайшие солдаты замялись, орудийный ездовой остановил свою лошадь, но сзади всё еще слышались крики: «Пошел на лед, что стал, пошел! пошел!» И крики ужаса послышались в толпе. Солдаты, окружавшие орудие, махали на лошадей и били их, чтобы они сворачивали и подвигались. Лошади тронулись с берега. Лед, державший пеших, рухнулся огромным куском, и человек сорок, бывших на льду, бросились кто вперед, кто назад, потопляя один другого.
Ядра всё так же равномерно свистели и шлепались на лед, в воду и чаще всего в толпу, покрывавшую плотину, пруды и берег.


На Праценской горе, на том самом месте, где он упал с древком знамени в руках, лежал князь Андрей Болконский, истекая кровью, и, сам не зная того, стонал тихим, жалостным и детским стоном.
К вечеру он перестал стонать и совершенно затих. Он не знал, как долго продолжалось его забытье. Вдруг он опять чувствовал себя живым и страдающим от жгучей и разрывающей что то боли в голове.
«Где оно, это высокое небо, которое я не знал до сих пор и увидал нынче?» было первою его мыслью. «И страдания этого я не знал также, – подумал он. – Да, я ничего, ничего не знал до сих пор. Но где я?»
Он стал прислушиваться и услыхал звуки приближающегося топота лошадей и звуки голосов, говоривших по французски. Он раскрыл глаза. Над ним было опять всё то же высокое небо с еще выше поднявшимися плывущими облаками, сквозь которые виднелась синеющая бесконечность. Он не поворачивал головы и не видал тех, которые, судя по звуку копыт и голосов, подъехали к нему и остановились.
Подъехавшие верховые были Наполеон, сопутствуемый двумя адъютантами. Бонапарте, объезжая поле сражения, отдавал последние приказания об усилении батарей стреляющих по плотине Аугеста и рассматривал убитых и раненых, оставшихся на поле сражения.