Теорема. Метод математической индукции

Теорема

Пусть имеется последовательность утверждений $P_n$ определённых для каждого натурального $n$, которые требуется доказать. Метод математической индукции, который мы будем использовать, состоит из следующих действий.

1. База индукции.

Подразумевает доказательство $P_1$ т.е. первого утверждения (иногда последовательность начинается с 0 или наоборот с числа, большего единицы; это не меняет сути метода, т.к. всегда имеется возможность условной перенумерации).

2. Индуктивный переход.

Доказывается условное утверждение: $P_k⟹P_{k+1}$.

Таким образом, идея заключается в следующем: если верно первое утверждение, то благодаря индуктивному переходу верны и все остальные.

Примеры

1. Докажем факт: для любого $n\in \mathbf{N}$ число $4^n-1$ делится на 3 .
   • База индукции: $n=1$. $4^1-1=3,\text{ делится на }3$
   • Индуктивный переход: пусть утверждение выполнено для $k\in \mathbf{N}:\left(4^k-1\right):3$. Докажем для $k+1$ :$4^{k+1}-1=4^k\cdot 4-4+3=4\left(4^k-1\right)+3$ Оба слагаемых делятся на 3 , значит, делится и всё выражение.
2. Докажем теперь, что для любого $n\in \mathbf{N}$ верно равенство$1^3+2^3+3^3+\dots +n^3=\frac{n^2(n+1{)}^2}{4}$
   • База индукции: n = 1 $1^3=1=\frac{1^2\cdot 2^2}{4}$
   • Индуктивный переход: пусть утверждение выполнено для $k\in \mathbf{N}$, докажем для $k+1$ : $\begin{array}{l}(1^3+2^3+3^3+\dots +k^3)+(k+1{)}^3=\frac{k^2(k+1{)}^2}{4}+(k+1{)}^3=(k+1{)}^2(\frac{k^2}{4}+k+1)=\\ =\frac{(k+1{)}^2(k^2+4k+4)}{4}=\frac{(k+1{)}^2(k+2{)}^2}{4}\end{array}$что и требовалось получить
3. Рассмотрим пример индукции в геометрии.
   Докажем, что $n$ прямых в общем положении (т.е. никакие две из них не параллельны и никакие три не пересекаются в одной точке) делят плоскость на $\frac{n^2+n+2}{2}$ частей.

   • База индукции: $n=1$.
     Одна прямая делит плоскость на $\frac{1+1+2}{2}=2$ части.

   • Индуктивный переход: предположим, что $k$ прямых делят плоскость на $\frac{k^2+k+2}{2}$ частей, докажем, что $k+1$ прямая делит плоскость на $\frac{(k+1{)}^2+(k+1)+2}{2}$ частей.

   Доказательство индуктивного перехода

Итак, проведём ещё одну прямую и посмотрим, как увеличится число частей плоскости. Будем проводить прямую из “бесконечности”, т.е. оттуда, где она ещё не встречает ни одной другой прямой. Когда она впервые пересечёт другую прямую, добавится одна новая часть плоскости. Таких пересечений будет $k$, значит, пересекая $k$ прямых, она отсечёт $k$ новых областей плоскости. Затем, после пересечения последней прямой, она опять уйдёт “в бесконечность” с другой стороны, разбив ещё одну часть плоскости на две.
Таким образом, к имеющимся частям плоскости добавится ещё $k+1$ : $\begin{array}{l}\frac{k^2+k+2}{2}+(k+1)=\frac{k^2+3k+4}{2}=\frac{\left(k^2+2k+1\right)+(k+1)+2}{2}=\frac{(k+1{)}^2+(k+1)+2}{2}\end{array}$

дополнительно