Метод математической индукции
Чтобы доказать утверждение с помощью метода математической индукции, необходимо проверить два условия:
1. Базис индукции (База индукции):
- утверждение верно для \(\displaystyle n=1\small.\)
2. Индуктивный шаг (Индукционный переход):
- из справедливости утверждения для \(\displaystyle n=k\) следует его справедливость для \(\displaystyle n=k+1\small.\)
Пример
Докажем по индукции утверждение:
Сумма первых \(\displaystyle n\) натуральных чисел равна \(\displaystyle \frac{n(n+1)}{2}{\small:}\)
\(\displaystyle 1+2+3+\ldots+n=\frac{n(n+1)}{2}\small.\)
1. Базис индукции. Утверждение должно быть верно для всех натуральных \(\displaystyle n{ \small .} \) Значит, сначала необходимо проверить утверждение для \(\displaystyle n=1{\small.}\)
Получаем:
\(\displaystyle 1=\frac{1\cdot(1+1)}{2}\small.\)
Правая часть равна \(\displaystyle \frac{1\cdot(1+1)}{2}=\frac{2}{2}=1\small,\) то есть утверждение верно для \(\displaystyle n=1\small.\)
2. Индуктивный шаг. Предполагая, что утверждение верно для \(\displaystyle n=k\small,\) необходимо проверить его для \(\displaystyle n=k+1\small.\)
Запишем левую часть для \(\displaystyle n=k+1{\small:}\)
\(\displaystyle 1+2+3+\ldots+k+(k+1)\small.\)
По предположению индукции (утверждение верно для \(\displaystyle n=k\)) сумма первых \(\displaystyle k\) слагаемых равна \(\displaystyle \frac{k(k+1)}{2}{\small:}\)
\(\displaystyle 1+2+3+\ldots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)\small.\)
Приведем слагаемые к общему знаменателю:
\(\displaystyle \frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+2)(k+1)}{2}\small.\)
То есть
\(\displaystyle 1+2+3+\ldots+k+(k+1)=\frac{(k+1)((k+1)+1)}{2}\small.\)
Значит, утверждение верно и для \(\displaystyle n=k+1\small.\)
Таким образом, утверждение доказано.