Кратко — способ проверки, когда индуктивный шаг зависит от чётности $n$, и как это формализовать.
1) Идея и когда оправдано
- Оправдано, когда утверждение $P(n)$ для следующего значения зависит от того, чётно или нечётно текущее $n$ (или когда рекуррентная зависимость «через два шага»).
- Эквивалентно обычной индукции: всякая «парная/непарная» схема сводится к индукции по $m=\lfloor n/2\rfloor$ или к двум параллельным утверждениям для классов по модулю $2$.
2) Две стандартные формализации
- Вариант A (индукция с шагом $2$):
- Докажите базисы $P(0)$ и $P(1)$.
- Покажите $\forall n(P(n)\Rightarrow P(n+2))$.
- Тогда по обычной индукции получаем $P(n)$ для всех $n$ (покрываются все чётные и нечётные индексы).
- Вариант B (одновременная индукция для двух предикатов):
- Определите $E(m):=P(2m)$, $O(m):=P(2m+1)$.
- Докажите $E(0)$ и $O(0)$.
- Докажите $\forall m(E(m)\Rightarrow O(m))$ и $\forall m(O(m)\Rightarrow E(m+1))$.
- Применив обычную индукцию по $m$ к паре $(E(m),O(m))$, получаете $P(n)$ для всех $n$.
(Эта формализация удобна, когда шаги явно переходят «чётное→нечётное» и «нечётное→чётное».)
3) Как проверять корректность доказательства — чеклист
- Базовые случаи: явно проверьте все малые $n$ (минимум $0$ и $1$, или все случаи до максимального шага минус один).
- Покрытие: убедитесь, что комбинация базисов и переходов действительно покрывает все натуральные числа (показывается формально в вариантах A или B).
- Корректное использование гипотезы: в каждом переходе используйте только те утверждения, которые уже гарантированы предыдущими шагами (не ссылаться на $P(n+2)$ при доказательстве $P(n+1)$).
- Порядок и направление: если переходы строятся как $E(m)\Rightarrow O(m)$ и $O(m)\Rightarrow E(m+1)$, проверьте, что в доказательстве импликаций аргументы зависят от $m$ в правильном направлении.
- Особые мелкие случаи: если для малых $n$ логика перехода не годится (особые коэффициенты, деление на ноль и т.д.), внесите отдельные база-кейсы.
4) Когда нужен сильный вариант
- Если доказательство $P(n+1)$ требует знаний о нескольких предыдущих значениях $P(k)$ для $k\le n$ (не только $n$ или $n-1$), используйте сильную индукцию или расширьте базис на первые несколько значений (например, $P(0),P(1),\dots ,P(t-1)$) и покажите $\forall n(P(0)\wedge \cdots \wedge P(n)\Rightarrow P(n+1))$.
5) Формальное обоснование в Пеано-теории / логике
- Любая схема с шагом $2$ сводима к стандартной индукции по $m$ через отображение $n\mapsto m=\lfloor n/2\rfloor$ или через предикаты $E(m),O(m)$. Это даёт формальную гарантию дедукции в арифметике пэано.
Короткое резюме: проверьте базисы для обеих чётности, формализуйте либо как индукцию с шагом $2$ ($P(0),P(1),P(n)\Rightarrow P(n+2)$), либо как одновременную индукцию на парах $E(m),O(m)$; контролируйте корректность использования гипотез и при необходимости применяйте сильную индукцию.