🁢Из жизниПредставь бесконечную цепочку костяшек домино. Чтобы упали все, достаточно двух вещей: столкнуть первую костяшку — и убедиться, что каждая падающая костяшка обязательно толкает следующую. Если оба условия выполнены — упадут все костяшки без исключения, сколько бы их ни было. Это и есть идея математической индукции: способ доказать утверждение сразу для всех натуральных $n$, не проверяя их по одному.
Принцип математической индукции
📐Принцип индукцииЕсли утверждение, зависящее от натурального $n$: 1) верно при $n=1$ (база индукции — «первая костяшка падает»), 2) из его истинности при $n=k$ следует истинность при $n=k+1$ (индукционный переход — «падающая костяшка толкает следующую»), — то оно верно для любого натурального $n$.
Пример: сумма нечётных чисел
Докажем, что сумма первых $n$ нечётных чисел равна $n^2$:
$$1 + 3 + 5 + \ldots + (2n-1) = n^2$$
Разбери доказательство по шагам на интерактиве справа — там же наглядно показано, как каждый следующий шаг «выкладывает» квадрат из точек.
1
База ($n=1$): слева одно слагаемое $1$, справа $1^2=1$ — равенство верно.
2
Предположение: допустим, при $n=k$ равенство верно: $1+3+\ldots+(2k-1)=k^2$.
3
Переход к $n=k+1$: прибавим к обеим частям $(2k+1)$:
$$1+3+\ldots+(2k-1)+(2k+1) = k^2+(2k+1) = (k+1)^2$$
Получили в точности исходное равенство при $n=k+1$ — переход доказан.
По принципу индукции равенство верно для любого натурального $n$. $\blacksquare$
Ещё примеры
Степени. Если $a>0$, то $a^n>0$ для любого $n$: при $n=1$ верно по условию; если $a^k>0$, то $a^{k+1}=a^k\cdot a>0$ (произведение положительных).
Неравенство Бернулли. При $b \ge -1$ для любого натурального $n$: $(1+b)^n \ge 1+nb$. При $n=1$ — равенство. Переход: $(1+b)^{k+1}=(1+b)^k(1+b) \ge (1+kb)(1+b) = 1+(k{+}1)b+kb^2 \ge 1+(k{+}1)b$.
⚠️Частая ошибкаОба шага доказательства обязательны — нельзя пропускать ни один. Без базы «доказывают» и заведомо неверные утверждения: если предположить $2^{n+1}<2^n$ верным при $n=k$, то при умножении на $2$ оно останется верным и при $n=k+1$ — но база при $n=1$ не выполняется, и вывод в целом неверен. Без перехода формула $p=n^2-n+41$ даёт простые числа при $n=1,2,\ldots,40$, но уже при $n=41$ получается составное число $41^2$ — проверка нескольких первых значений не гарантирует справедливости для всех $n$.
Запомни
🧠Метод математической индукции
шаг 1 — проверить базу при $n=1$ (или при начальном $n_0$, если утверждение верно не с единицы);
шаг 2 — предположить верность при $n=k$ и вывести из неё верность при $n=k+1$;
оба шага обязательны — пропуск любого из них делает доказательство неверным;
метод доказывает утверждение сразу для всех натуральных $n$, а не только для проверенных значений.