3. Мат. индукция

Определение

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

Определение

База индукции - это проверка истинности доказываемого утверждения \(P(n)\) для начального значения натурального числа. Чаще всего это \(n=1\), но в зависимости от условия задачи база может начинаться с \(n=0\), \(n=2\) или любого другого числа \(n_0\)

Алгоритм решения задач

Доказать истинность для начального значения \(n\)
Предположить истинность при каком-то произвольном натуральном \(n=k\)
Доказать истинность для \(k+1\) исходя из пункта 2
Сделать вывод что утверждение выполняется для всех натуральных чисел

Примеры

Пример 1

Докажем методом математической индукции следующее устверждение(сумма n натуральных чисел):

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

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

Пусть \(n=1\), тогда:

\[ 1 = \frac{1(1+1)}{2} \Rightarrow 1 = 1 \]

Утверждение истинно, база индукции есть

2. Индукционное предположение

Предпологаем что следующее выражение истинно:

\[ P(k): \quad 1+2+3+ ... + k = \frac{k(k+1)}{2} \]

3. Шаг индукции

теперь нам необходимо доказать истинность при \(k+1\)

\[ 1+2+3+...+k+(k+1) = \frac{(k+1)(k+1+1)}{2} \]

\[ 1+2+3+...+k+(k+1) = \frac{(k+1)(k+2)}{2} \]

Берём левую часть \(P(k+1)\) и используем индукционное предположение \(P(k)\):

\[ \underbrace{1+2+3+...+k}_{\frac{k(k+1)}{2} \quad \text{из пункта 2}}+(k+1) = \frac{k(k+1)}{2}+(k+1) \]

Выносим за скобку \(k+1\)

\[ (k+1)\left(\frac{k}{2} + 1 \right) = (k+1)\left(\frac{k+1}{2}\right) = \frac{(k+1)(k+2)}{2} \]

это полностью совпадает с правой частью, следовательно выражение истинно

4. Вывод

По принципу математической индукции, формула верна для всех натуральных \(n\)