数学归纳法

基例给出可以开始的地方，归纳步给出不会中断的推进规则。假如仍有失败位置，自然数的良序性会给出最小失败位置；它不可能是起点，而其前一位置已成功，归纳步又迫使它成功，矛盾。

归纳假设不是先承认整个结论。要证明条件句 $P(n)\Rightarrow P(n+1)$，允许临时使用它的前提，就像任何条件证明一样；最后把基例和任意 $n$ 的条件句结合，才得到全称结论。检查前一百个例子无法替代任意 $n$ 的证明。

累积和怎样接到下一项 ​

证明对所有 $n\ge 0$，

$n=0$ 时两边都是 $1$。现在固定任意 $n\ge 0$，假设结论对这个 $n$ 成立，则

第一步将新问题分成旧问题加一个新项，第二步才使用归纳假设；末式恰好是把原命题中的 $n$ 换成 $n+1$。同一拆分也证明 $1+\cdots +n=n(n+1)/2$，其归纳步的代数核心是 $n(n+1)/2+(n+1)=(n+1)(n+2)/2$。

覆盖范围不能有缺口 ​

若只证明 $P(n)\Rightarrow P(n+2)$，则从一个基例只能沿一个奇偶类前进。例如“$n$ 为偶数”在 $0$ 成立且对加二封闭，却显然不对所有自然数成立；要覆盖全部自然数需要两个起点。同样，证明从 $1$ 开始，不能声称同时覆盖 $0$。

经典的“所有马颜色相同”错误证明把 $n+1$ 匹马去掉首匹、末匹，得到两组各 $n$ 匹马，再用两组共同的马连接颜色。漏洞正发生在 $n=1$：两组各一匹却没有交集，无法连接。后续步骤看起来可行，仍不能弥补最早的断点。

普通归纳与强归纳理路强归纳法Strong induction · Complete induction归纳步可假设所有较小自然数情形成立。在自然数上的证明能力相同。强归纳直接允许使用全部较小索引的结论；若只有普通归纳，可改证

先在 $n=n_0$ 处使用强归纳前提中的步进条件：没有更小索引需要假设，直接得到 $P(n_0)$，也就得到 $Q(n_0)$。随后同一步进条件让 $Q(n)$ 推出 $P(n+1)$，连同原有 $Q(n)$ 得到 $Q(n+1)$，从而完成普通归纳。反向则更直接：全部先前结论当然包含紧邻前项。这个打包过程解释了“强”增加的是使用上的方便，而不是在这里加入更强公理。

归纳用于递推式、有限组合结构及递归算法正确性理路算法正确性Algorithm correctness · Partial and total correctness所有合法执行都符合规格，并在完全正确时保证终止。。良基归纳和结构归纳将索引从自然数改成其他良基结构，需要相应的前驱或构造规则。状态系统中的归纳不变式理路不变式与归纳不变式Invariant · Inductive invariant · Strengthened invariant区分所有可达状态上成立的性质与由初始性和一步闭包直接证明的归纳不变式。要求性质覆盖每个初始状态，并被每条转移保持，才可归纳得到所有有限步可达状态都满足性质。搜索有限样本或模型检查的部分状态不能替代这两个证明义务。