强归纳法

分解一个规模为 $n$ 的对象时，子对象未必恰好有规模 $n-1$。一个合数分成两个较小因子，递归算法分成大小不同的子问题，都希望能调用所有较小规模已经成立的结论。强归纳把这些结论同时开放给当前一步使用。

“强”指归纳假设更方便，不表示能证明普通归纳无法证明的自然数命题。它与普通归纳理路数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。的等价性，可由“把此前全部成立打包成一个新性质”看出。

素数分解的存在性 ​

证明每个整数 $n\ge 2$ 都是有限个素数的乘积。起点 $2$ 本身是素数。设 $n>2$ 且所有 $2\le k<n$ 的情况成立：若 $n$ 是素数，一个因子的乘积已经足够；否则按合数定义可写 $n=ab$，其中 $2\le a,b<n$。归纳假设分别给出 $a$、$b$ 的素数分解，把两列因子连接便得到 $n$ 的分解。

例如 $12=3\cdot 4$，可调用较小规模 $3$ 和 $4$，得到 $12=3\cdot 2\cdot 2$。证明并不依赖刚好前一个数 $11$。它只保证分解存在；不同分解的因子是否一致，是唯一性部分的另一个问题。

为什么有时必须验证多个起点 ​

证明每个 $n\ge 8$ 都可写为 $3a+5b$，其中 $a,b$ 是非负整数。先验算

当 $n\ge 11$ 时，$8\le n-3<n$，故由归纳假设有 $n-3=3a+5b$，再加 $3$ 得 $n=3(a+1)+5b$。对于 $n=11$，实际使用的是 $8$ 的表示；对于 $12$、$13$，则分别需要 $9$、$10$。只验 $8$ 会留下另外两个余数类的缺口。

归纳步必须确实减小指标。若一个递归调用仍指向 $n$，或者指向 $n+1$，不能声称已有强归纳假设；那会把未证结论当作前提，形成循环。

要由普通归纳得到强归纳，令 $Q(n)$ 表示“所有 $n_0\le k\le n$ 都满足 $P(k)$”。基例是 $P(n_0)$；若 $Q(n)$ 成立，强归纳的步进假设给出 $P(n+1)$，合起来就是 $Q(n+1)$。反向转换更直接：全部较小情形包含紧邻的前一情形，因此普通归纳步可作为强归纳步使用。

另一种等价写法是最小反例法：若有失败的自然数，取最小的一个，它之前的情况都成功，归纳步却又迫使它成功，矛盾。这依赖自然数通常次序的良序性质；不是断言任意集合可赋予良序的良序定理理路良序定理Well-ordering theorem · Zermelo's theorem每个集合都能赋予一个使任意非空子集具有最小元的全序。，不需要选择公理。

分治与动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。的正确性常按输入规模强归纳。若索引是树或其他关系，应改用相应的结构归纳或良基归纳，并核查“更小”的关系为何保证每个非空反例集合有极小元。