В широком, логическом смысле этого слова под \(\textbf{индукцией}\) понимается логическое построение, позволяющее из частных соображений об объекте сделать некоторый глобальный вывод об этом самом объекте.

В контексте математики довольно обширное применение имеет \(\textbf{метод математической индукции}\), заключающийся в следующем.

Рассмотрим серию утверждений, занумерованных натуральными числами: \((P_1, P_2, ...)\). Согласно методу математической индукции (далее \(- \textbf{ПМИ}\)), если утверждение \(P_1\) верно (\(\textbf{база индукции}\)), а также если из верности \(P_{n-1}\) следует \(P_n\) для любого \(n\) (\(\textbf{шаг индукции}\)), то любое утверждение \(P_i\) верно.

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

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

Серия утверждений \(\{P_i\}\), о которой мы говорили ранее, может быть занумерована и при помощи более богатого множества вещественных чисел. В таком случае говорят о \(\textbf{трансфинитной индукции.}\)

\(\textbf{Пример:}\)

Покажем, что

\[1 + 2 + 3 + ... + n = \dfrac{n(n+1)}{2}\]

Проверим базу индукции, то есть справедливость данного утверждения для \(n=0: \,\,\,\, 0 = \dfrac{0 \cdot (0+1)}{2} = 0\).

Пусть наше равенство верно для некоторого натурального \(k\):

\[0+1+2+...+k = \dfrac{k\cdot (k+1)}{2}\]

Покажем, что оно тогда будет верно и для \(k+1\):

\[0+1+2+...+k + (k+1) = \dfrac{k\cdot (k+1)}{2} + (k+1)\]

Преобразуем теперь правую часть, приведя к общему знаменателю:

\[\dfrac{k\cdot (k+1)}{2} + (k+1) = \dfrac{k\cdot (k+1) + 2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2} = \dfrac{(k+1)((k+1)+1)}{2}\]

Доказали индуктивный переход. Это значит, что исходная формула верна для любых \(n\), что завершает наше доказательство.

Обозначение: ПМИ, ММИ