Потенциальная ошибка — неявное обращение к «отдельным» доказательствам шага индукции для каждого конкретного $n$ вместо единого доказательства универсальной импликации. Формулировка «если для всех $n$ верно: из $P(n)$ следует $P(n+1)$» должна быть понята как утверждение с универсальным квантором (или как единый доказуемый шаг с параметром $n$), иначе можно иметь для каждого конкретного $n$ свой частный вывод $P(n)\Rightarrow P(n+1)$, не дающий единой цепочки выводов.
Исправленная формулировка (стандартная теорема индукции):
- Пусть $P(n)$ — свойство, зависящее от натурального числа $n$.
- Если выполнены оба условия:
1. $P(1)$ истинно;
2. для всех натуральных $k$ истинно $P(k)\Rightarrow P(k+1)$,
то тогда для всех натуральных $n$ истинно $P(n)$.
Эквивалентная форма (через множества):
- Пусть $S\subset \mathbb{N}$. Если $1\in S$ и $\forall n\in \mathbb{N}(n\in S\Rightarrow n+1\in S)$, то $S=\mathbb{N}$.
Короткое пояснение: важно, чтобы условие шага индукции было универсальным (или имелось единое доказательство с параметром $n$), тогда от базового случая $P(1)$ последовательно следует $P(2),P(3),\dots$. Эти формулировки эквивалентны аксиоме индукции и принципу хорошего упорядочения.