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

Математи́ческая инду́кция, метод доказательства математических утверждений, основанный на следующем принципе: утверждение ${\displaystyle A(x)}$, зависящее от натурального параметра ${\displaystyle x}$, считается доказанным для всех натуральных ${\displaystyle x}$, если доказано утверждение ${\displaystyle A(1)}$, и для любого натурального числа ${\displaystyle n}$ из предположения, что верно утверждение ${\displaystyle A(n)}$, следует, что верно также утверждение ${\displaystyle A(n+1)}$. Этот принцип называется принципом математической индукции.

Пример. Пусть для любого натурального числа ${\displaystyle n}$ требуется доказать формулу

${\displaystyle 1+3+5+\ldots +(2n-1)=n^{2}.}$ (1)

При ${\displaystyle n=1}$ эта формула даёт верное равенство ${\displaystyle 1=1^{2}}$. Чтобы доказать правильность формулы (1) при любом ${\displaystyle n}$, допускают, что её уже удалось доказать для некоторого натурального числа ${\displaystyle N}$, т. е. предполагают, что

${\displaystyle 1+3+5+\ldots +(2N-1)=N^{2},}$ (2)

и, опираясь на это допущение, доказывают правильность формулы (1) для числа ${\displaystyle n=N+1}$. В данном случае достаточно добавить к правой и левой частям равенства (2) слагаемое ${\displaystyle 2N+1}$, при этом получится равенство

${\displaystyle 1+3+5+\ldots +(2N-1)+(2N+1)=N^{2}+(2N+1)}$.

Так как правая часть этого равенства есть${\displaystyle (N+1)^{2}}$, то из справедливости (1) при ${\displaystyle n=N}$ вытекает справедливость (1) при ${\displaystyle n=N+1}$ (каково бы ни было ${\displaystyle N}$), т. е. (1) справедливо при всех натуральных ${\displaystyle n}$.

Доказательство утверждения ${\displaystyle A(1)}$ составляет первый шаг (базис) индукции, а доказательство утверждения ${\displaystyle A(n+1)}$ в предположении, что верно ${\displaystyle A(n)}$, называется шагом индукции или индукционным переходом. При этом ${\displaystyle n}$ называется параметром индукции, а предположение ${\displaystyle A(n)}$ при доказательстве утверждения ${\displaystyle A(n+1)}$ называется индуктивным предположением.

Принцип математической индукции является также основанием для индуктивных определений. Простейшим примером такого определения является определение свойства «быть словом длины ${\displaystyle n}$ в данном алфавите ${\displaystyle {\mathcal {A}}=\{a_{1},a_{2},...,a_{k}\}}$». Базис индукции: каждая буква алфавита ${\displaystyle {\mathcal {A}}}$ есть слово длины ${\displaystyle 1}$. Индукционный переход: если ${\displaystyle E}$ – слово длины ${\displaystyle n}$ в ${\displaystyle {\mathcal {A}}}$, то каждое слово ${\displaystyle Ea_{i}}$, где к слову ${\displaystyle E}$ справа приписывается буква ${\displaystyle a_{i}}$, где ${\displaystyle 1\leqslant i\leqslant k}$, есть также слово длины ${\displaystyle n+1}$ в ${\displaystyle {\mathcal {A}}}$. Индукция может начинаться с ${\displaystyle n=0}$, т. е. с пустого слова.

Математическая индукция может применяться для доказательства утверждений ${\displaystyle A(x)}$, в которых параметр ${\displaystyle x}$ пробегает то или иное множество, вполне упорядоченное по некоторому трансфинитному типу; в этом случае говорят о трансфинитной индукции.