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

Материал из Википедии — свободной энциклопедии

Математическая индукция — в математике, один из методов доказательства. Его можно описать следующим образом.

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

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

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

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

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

[править] Пример

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

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

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

База, n = 1:

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

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

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

тогда

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

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

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

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

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

[править] Обобщения

Трансфинитная индукция

[править] Литература

Н.Я. Виленкин Индукция. Комбинаторика. Пособие для учителей. М., Просвещение, 1976.—48 с.
Л.И. Головина, И.М. Яглом Индукция в геометрии, «Популярные лекции по математике», Выпуск 21, Физматгиз 1961.—100 с.
Р. Курант, Г. Роббинс «Что такое математика?» Глава I, § 2.
И.С. Соминский Метод математической индукции. «Популярные лекции по математике», Выпуск 3, Издательство «Наука» 1965.—58 с.