Коротко о принципе: для доказательства утверждения $P(n)$ для всех $n\ge n_0$ нужно два элемента:
- правильная база индукции: $P(n_0)$ (и, при необходимости, несколько первых $P(n_0),\dots ,P(n_0+r-1)$);
- корректно сформулированный индуктивный шаг: показать, что из подходящих предположений о меньших значениях следует $P(n+1)$.
Ошибки возникают, когда база слишком слаба или шаг индукции тайно использует больше, чем заявлено в предположении.
Пример 1 (классическая «ошибка с лошадьми»).
Утверждение: $P(n)$ — «в любой коллекции из $n$ лошадей все лошади одного цвета».
Ошибочное доказательство:
- База: $P(1)$ верно.
- Шаг: пусть $P(n)$ верно. Рассмотрим $n+1$ лошадей. Уберём первую — остаётся набор $A$ из $n$ лошадей, по предположению в $A$ все одной краски. Уберём последнюю — остаётся набор $B$ из $n$ лошадей, в $B$ тоже одна краска. Поскольку $A\cap B$ содержит (якобы) хотя бы одну лошадь, цвета совпадают и значит все $n+1$ лошадей одной краски. Следовательно $P(n+1)$.
Где провал: при переходе $n=1\to n+1=2$ множества
$$A=\{\text{вторая лошадь}\},B=\{\text{первая лошадь}\}$$ пересекаются в пустом множестве: $A\cap B=\varnothing$. Тогда вывод о наличии общей лошади неверен, и контрпример (две лошади разного цвета) опровергает «доказательство».
Как исправить: расширить базу. Если подтвердить одновременно $P(1)$ и $P(2)$, то для любого $n\ge 2$ при переходе $n\to n+1$ множества $A$ и $B$ имеют пересечение размера $n-1\ge 1$, т.е. аргумент становится корректным. Иначе нужно изменить аргументацию, не полагаясь на непроверяемое пересечение.
Пример 2 (нужна сильная индукция).
Утверждение: «каждое целое $n\ge 2$ раскладывается в произведение простых чисел».
Невнимательный (слабый) шаг: предположим только $P(k)$ и пытаемся доказать $P(k+1)$. Если $k+1$ простое — тривиально. Если составное, $k+1=ab$ с $2\le a,b\le k$. Чтобы разложить $k+1$ на простые, нам нужно разложить $a$ и $b$. Но эти числа могут быть меньше $k$, а слабая индукция даёт нам информацию только о $k$, не о всех меньших числах. Следовательно строгий вывод не выполняется.
Правильный подход: использовать сильную (полную) индукцию: как индуктивное предположение принимать, что $P(m)$ верно для всех $2\le m\le k$. Тогда для составного $k+1=ab$ мы имеем разложения для $a$ и $b$ по предположению, отсюда разложение для $k+1$. База — $P(2)$ — проверяется отдельно.
Короткие общие рекомендации:
- Проверьте базовые случаи до такой глубины, на какую «опирается» ваш индуктивный шаг (если шаг переходит на $+r$, нужны $r$ базовых случаев).
- Явно указывайте, какие значения предполагаются в индуктивном предположении (слабая или сильная индукция).
- В индуктивном шаге не скрывайте дополнительных предположений (например, о непустом пересечении множеств или о свойствах промежуточных чисел).
Так вы избежите «ложных доказательств» и сможете исправить ошибочные построения.