强归纳法

强归纳在证明 $P(n)$ 时允许使用所有较小索引 $P(0),\dots ,P(n-1)$，而不只前一个规模；这正好匹配递归算法或组合对象分解成多个不同大小子问题的结构。它与普通归纳等价：把“到 $n$ 为止全部成立”打包成新命题即可互相转换。所谓强弱只是使用方式不同，不是证明能力的差异。

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

证明每个 $n\ge 8$ 都能写成 $3a+5b$，其中 $a,b\in \mathbb{N}$。先验证 $8=3+5$、$9=3+3+3$、$10=5+5$；当 $n\ge 11$ 时，$n-3\ge 8$，由强归纳假设把 $n-3$ 写成 $3a+5b$，再补一个 $3$ 即得 $n$ 的表示。这里归纳步调用的是 $P(n-3)$，所以必须同时覆盖连续的三个起点；这一方法的边界正是起点覆盖范围，只验证 $n=8$ 而直接向后推进会留下 $9,10$ 的缺口。

普通归纳公理库数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。与强归纳可互推，良序原理公理库良序定理Well-ordering theorem · Zermelo's theorem每个集合都能赋予一个使任意非空子集具有最小元的全序。又给出最小反例版本。递归定义与算法、树结构、整数分解、动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。和分治正确性，常自然使用全部较小规模的归纳假设；良基归纳则把自然数的“小于”替换为任意不存在无穷下降链的关系。