Кратко идея «доказательства»: утверждение $P(n)$ — «всякий набор из $n$ натуральных чисел состоит из одинаковых чисел». Базис: $P(1)$ очевидно. Индукционный шаг (как его дают): пусть $P(k)$ верно; взять набор из $k+1$ чисел, убрать первый — по $P(k)$ оставшиеся $k$ равны; убрать последний — те $k$ тоже равны; поскольку оба $k$-набора пересекаются, все $k+1$ равны.
Точная ошибка: этот аргумент требует, чтобы два $k$-набора имели непустое пересечение. Для $k=1$ (переход $1\to 2$) пересечение двух односоставных наборов пусто, и вывод о равенстве сделать нельзя. Формально: при $k$ пересечение имеет размер $k-1$, т.е. для $k=1$ размер пересечения $k-1=0$. Следовательно индукционный шаг не выполняется для $k=1$.
Правильное условие индукции, исправляющее ловушку: либо
- докажите базисы $P(1)$ и $P(2)$, и затем докажите импликацию $P(k)\Rightarrow P(k+1)$ только для всех $k\ge 2$; тогда по индукции получаете $P(n)$ для всех $n\ge 1$ (но в данном случае это даст ложный вывод, потому что $P(2)$ неверно — значит доказательство наталкивается на противоречие),
или явнее:
- при применении данного приёма требуйте в индукционном шаге условие $k\ge 2$, поскольку только тогда пересечение двух $k$-подмножеств размера $k-1$ нетривиально.
Как избегать такой ловушки:
- всегда проверяйте, для каких минимальных значений $k$ индукционный шаг корректен; при необходимости добавьте дополнительные базовые случаи до этого минимума;
- явно указывайте и проверяйте скрытые предположения (например, что пересечение непусто);
- при сомнении используйте сильную индукцию с явно перечисленными начальными шагами или приведите контрпример (например, $1\ne 2$), чтобы убедиться, что утверждение вообще истинно.
Итог: ошибка — в переходе $1\to 2$ (пересечение пусто). Исправление — сделать базовые случаи достаточными (проверить и $P(2)$) или изменить область применения индукционного шага и явным образом контролировать скрытые предпосылки.