Кратко о различии
- Обычная (слабая) индукция: базовый шаг — доказать $P(1)$ (или несколько первых), индукционный шаг — предположить $P(k)$ и вывести $P(k+1)$.
- Сильная (полная) индукция: базовые шаги — доказать несколько начальных $P(1),\dots ,P(m)$ (обычно $m=1$), индукционный шаг — предположить, что для некоторого $k$ верны все утверждения $P(1),P(2),\dots ,P(k)$ и на основе этого вывести $P(k+1)$.
Почему это отличается на практике: в обычном шаге вы можете оперировать только знанием о единственном предшественнике $k$; в сильной индукции вам разрешено использовать информацию о всех меньших числах. Формально обе формы эквивалентны; доказательство эквивалентности: положим $Q(n)$ как «для всех $m\le n$ верно $P(m)$». Применив обычную индукцию к $Q(n)$, получим сильную форму.
Типичные примеры, где нужна сильная индукция (или существенно удобнее)
1) Разложение на простые множители (основная теорема арифметики, существование):
- Утверждение: для всех $n\ge 2$ число $n$ представимо как произведение простых.
- Почему обычная индукция неудобна: при переходе от $k$ к $k+1$ число $k+1$ может быть составным и имеет делитель $d$ с $1<d<k+1$; чтобы применить предположение, нужно знать утверждение для числа $d$ и для $(k+1)/d$, т.е. для нескольких меньших значений, а не только для $k$.
- Кратный план доказательства с сильной индукцией: базовый случай $2$ прост. Для составного $n$ возьмём делитель $d$, по индукции представим $d$ и $(n/d)$ как произведения простых, перемножим.
2) Задача о плитках (тромино):
- Утверждение: доску $2^n\times 2^n$ с одним удалённым клеточным квадратом можно замостить L-образными трёхклеточными плитками для всех $n\ge 1$.
- Почему нужна сильная идея: при разбиении доски на четыре квадранта вы используете факт о меньших досках размера $2^{n-1}$ — это удобно формулировать и доказывать через сильную индукцию (хотя можно оформить и обычной, но по сути используется информация о «меньших» досках).
3) Почтовая задача / монеты:
- Утверждение типа: для монет номиналом $a$ и $b$ все суммы $\ge N$ можно получить; в доказательстве для суммы $S$ часто разбивают её на $S-x$ для некоторого $x\in \{a,b\}$ и используют утверждение для гораздо меньшей суммы, т.е. для произвольного меньшего числа.
4) Теорема Цекендорфа (разложение по числам Фибоначчи) — также доказывается сильной индукцией.
Как показать ученикам, зачем это нужно (методические приёмы)
- Показать пример, где обычная индукция «формально» применима, но «застревает» (попытка использовать только $P(k)$ не даёт перехода), затем показать, что если разрешить использовать все предыдущие случаи, доказательство становится естественным.
- Привести разложение на простые и пошагово попросить учеников попытаться сделать шаг, затем подсказать использовать знание для делителя $d$.
Последовательность упражнений (постепенный переход к сильной индукции)
Уровень A — закрепление слабой индукции
1) Докажите, что для всех $n\ge 1$ верно ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$. (Базовый пример.)
2) Докажите, что для всех $n\ge 0$ ${\sum }_{i=0}^n{r}^i=\frac{r^{n+1}-1}{r-1}$ для фиксированного $r\ne 1$.
3) Докажите, что для всех $n\ge 0$ верно $2^n\ge n+1$.
Уровень B — задачи, где удобно использовать несколько предыдущих случаев
4) Докажите, что для всех $n\ge 1$ выполнено $3^n\ge 2n+1$. (Показываем, что иногда нужен шаг с грубой оценкой, использующий $P(k)$ и базу.)
5) Докажите, что для всех $n\ge 2$ существует простой делитель числа $n$. (Вводим идею смотреть на произвольный нетривиальный делитель $d$ и требовать свойство для $d$.) Хинт: если $n$ составно, возьмите минимальный простой делитель или используйте индукцию по меньшим делителям.
Уровень C — сильная индукция напрямую
6) Разложение на простые: докажите, что для всех $n\ge 2$ число $n$ представимо как произведение простых. Хинт: для составного $n$ рассмотрите делитель $d$ с $1<d<n$; по индукции представьте $d$ и $n/d$.
7) Тромино: докажите, что любую доску $2^n\times 2^n$ с одной отсутствующей клеткой можно замостить L-троминоми. Хинт: разбиение на четыре квадранта и установка центрального тромино; затем примените индукционное предположение к четырём меньшим доскам.
8) Почтовая задача: для монет номиналом $4$ и $7$ докажите, что все суммы $\ge 18$ можно представить. Хинт: проверьте базовые случаи $\{18,19,20,21\}$, затем при переходе от $k\ge 21$ используйте, что $k-4$ уже представимо.
9) Теорема Цекендорфа (опционально, сложнее): доказать существование разложения в непоследовательные числа Фибоначчи.
Практические указания для преподавателя
- Перед задачами в уровне C дайте напоминание: «мы можем предположить все утверждения для всех чисел ≤$k$», объясните, почему это не «читерство» (формальная эквивалентность с обычной индукцией).
- На старте каждой сильной индукции явно обозначайте, какие базовые случаи нужны (часто несколько первых значений).
- Просите учеников формулировать, какую именно из предыдущих истин они используют при переходе $k\to k+1$ — это тренирует понимание, зачем именно нужна вся предшествующая информация.
Короткое доказательство эквивалентности (схема)
- Сильная ⇒ слабая: тривиально, потому что при предположении всех $P(1),\dots ,P(k)$ в частности есть $P(k)$.
- Слабая ⇒ сильная: пусть хотим доказать $\forall nP(n)$. Рассмотрим утверждение $Q(n)$: «для всех $m\le n$ верно $P(m)$». Покажите обычной индукцией, что $Q(n)$ верно для всех $n$. Тогда для каждого $n$ из $Q(n)$ следует $P(n)$.
Если нужно, могу развернуть любое из упражнений с полным решением и комментариями для урока.