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

Математическая индукция в математике — это один из методов доказательства утверждений.

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

Пусть дано подмножество натуральных чисел $A \subset \mathbb{N}.$ Пусть также справедливы следующие утверждения:

1. $1\in A;$
2. $\bigl(\{1,\ldots,n\} \subset A\bigr) \Rightarrow \bigl( n+1 \in A \bigr).$

Тогда $A = \mathbb{N}.$

Замечание

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

Доказательство методом математической индукции

Пусть имеется семейство утверждений $\{P(n)\}_{n\in \mathbb{N}}$. Пусть известно, что

1. (база индукции) $P(1)$ справедливо;
2. (индукционный переход) из справедливости $P(1),\ldots P(n)$ вытекает справедливость $P(n+1)$.

Тогда все утверждения $\{P(n)\}$ справедливы.

Пример

Покажем, что

$\forall n\in \mathbb{N}\; \forall q\in \mathbb{R}\setminus\{1\}\quad 1 + q + \cdots + q^n = \frac{1 - q^{n + 1}}{1 -q}.$

• Проверим базу индукции:

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

• Проведём индукционный переход. Предположим, что утверждение доказано для $m = 1,\ldots,n.$ Докажем его для $m=n+1.$

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

Таким образом утверждение верно для любого $n\in\mathbb{N}.$

Обобщения

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

Литература

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