数学归纳法
“归纳法是用两次检验，推倒无穷多张骨牌的技巧。”
公式
[ P(1) ∧ ( P(k) ⟹ P(k+1) ) ] ⟹ ∀n ≥ 1, P(n)怎么读: 如果第一种情形成立，并且每种情形成立都能推出下一种情形成立，那么这个命题对所有自然数都成立
- P(n)
- — 要对自然数 n 证明的命题
- P(1)
- — 基础步骤——推倒第一张骨牌
- P(k) ⟹ P(k+1)
- — 归纳步骤——每张骨牌都会推倒下一张
- ∀n ≥ 1
- — 因此对所有自然数都成立
引子
只用两行就能证明无穷多种情形——推倒第一张骨牌，证明每张骨牌都会推倒下一张，就大功告成。
通俗地说
数学归纳法用来证明「对每一个自然数 n」都成立的命题。（1）证明 n=1 时成立（基础步骤），（2）证明如果 n=k 时成立，那么 n=k+1 时也一定成立（归纳步骤）；就像多米诺骨牌，一旦推倒就全部倒下。
直觉
想象一排无穷无尽的多米诺骨牌。你不可能一张张亲手推倒。但你只需要确认两件事——第一张会倒，以及「只要任意一张倒了，它旁边那张也会倒」。于是第一张推倒第二张，第二张推倒第三张……一直倒下去，永无止境，所以全部会倒。用两次有限的检验，就征服了无穷。
如何构建
两个部分——基础步骤和归纳步骤。基础步骤直接验证起点（通常是 n=1）成立。归纳步骤则利用「假设 P(k) 成立」这一归纳假设，推出 P(k+1) 成立。两者缺一不可：没有第一张骨牌，什么都不会倒；没有传导链条，也只有一张会倒。
示例
证明 1+2+⋯+n = n(n+1)/2。基础 n=1：左边是 1 = 1·2/2 = 1 ✓。归纳：假设 1+⋯+k = k(k+1)/2，那么 1+⋯+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2，正好符合 n=k+1 时的公式 ✓。所以对所有 n 都成立。
常见误区
归纳假设「假设 P(k) 成立」看起来像循环论证——假设了你要证明的东西——但其实不是。你并不是在断言 P(k) 真的成立；你只是在证明「如果它成立，下一个也成立」这条条件链（骨牌之间的传导）。
用在哪里
证明求和公式与不等式、验证算法（递归和循环）的正确性、证明数据结构和编译器的正确性、数论与组合数学中的无数定理——凡是数学和计算机科学中出现「无穷多种情形」的地方，都少不了它。
从何而来
帕斯卡在 17 世纪研究帕斯卡三角形时明确使用了它，19 世纪皮亚诺又把它写进自然数的公理，使它成为逻辑学的一根支柱。
前置概念
小测验
除了基础步骤，数学归纳法还必须证明什么？
- 如果 P(k) 成立，那么 P(k+1) 也成立✓
- P(n) 对某一个较大的 n 成立
- P(n) 永远不会为假
- 不需要再证明别的
练习
用公式 1+2+⋯+n = n(n+1)/2 计算 1+2+⋯+10。
答案: 55
- 代入 n=10：10·11/2
- = 110/2 = 55
要点: 归纳法证明公式之后，直接代入即可。
计算 1+2+⋯+100。
答案: 5050
- 100·101/2
- = 10100/2 = 5050
要点: 相传就是少年高斯几秒钟内算出的那道求和题。
前 n 个奇数之和 1+3+5+⋯+(2n−1) = n²。求 n=5 时的值。
答案: 25
- 1+3+5+7+9 = 25
- = 5² = 25
要点: 奇数之和等于一个完全平方数——归纳法的经典例子。
用归纳法证明 1+2+⋯+n = n(n+1)/2（写出基础步骤和归纳步骤）。
答案: undefined
- 基础 n=1：1 = 1·2/2 = 1 ✓
- 假设：1+⋯+k = k(k+1)/2
- 加上 (k+1)：k(k+1)/2 + (k+1) = (k+1)(k+2)/2，正是 n=k+1 时的公式 ✓
要点: 基础步骤 + 归纳步骤 = 对无穷多种情形的完整证明。