形式陈述

设 $P(n)$$P(n)$ 对 $n\ge n_0$$n\ge n_0$ 定义。若对每个 $n\ge n_0$$n\ge n_0$，由

$$ P(n_0),P(n_0+1),\ldots,P(n-1) $$$$P(n_0),P(n_0+1),\dots ,P(n-1)$$

可推出 $P(n)$$P(n)$，则 $P(n)$$P(n)$ 对所有 $n\ge n_0$$n\ge n_0$ 成立。普通归纳与强归纳在自然数上等价；可令 $Q(n)=\bigwedge_{k=n_0}^{n}P(k)$$Q(n)=\underset{k=n_0}{\overset{n}{\bigwedge }}P(k)$ 相互转换。

直觉

证明当前规模时，可以使用所有更小规模的结论，而不只前一个规模。这与递归算法可能拆成任意较小子问题的结构匹配。

例子与边界

证明每个 $n\ge2$$n\ge 2$ 都可分解为素数乘积：若 $n$$n$ 非素，则 $n=ab$$n=ab$ 且 $2\le a,b<n$$2\le a,b<n$，可分别对 $a,b$$a,b$ 使用归纳假设。归纳步只能调用严格较小的指标；若直接假设 $P(n)$$P(n)$，证明会循环。

推论与应用

强归纳用于递归定义、数论分解、动态规划和分治正确性。良基归纳把自然数的“小于”替换为任意不存在无穷下降链的关系。

参考资料

• Richard Hammack, Book of Proof, 3rd ed., 2018, Chapter 10。
• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019, Mathematical Induction chapter。