数学归纳法
证明起点成立，再证明『成立能往下传』，于是对所有 n 成立。把一个无穷断言压缩成两件有限的事。
11 分钟思维方法: 归纳与递归
证明第一块骨牌会倒，再证明每块都会推倒下一块
这一片为什么存在
你算了前五个例子，全对，于是写下『显然对所有 n 成立』。圆周上取 n 个点两两连弦，分出的区域数是 1、2、4、8、16——第六个点却给出 31，不是 32。例子再多也盖不住无穷；可你又不可能一个一个验到底。归纳法就是为这个死局准备的：把无穷多次验证，换成两件有限的事。
内容
想象一排骨牌，无穷多块。你想说『每一块都会倒』。逐块检查做不完。但有两句话足够：第一块倒了；任何一块倒下都会撞倒它后面那块。第二句是一条局部规则——你不需要知道第 500 块长什么样、离得多远，只需要知道相邻两块之间的传递关系成立。
最容易卡住的是归纳假设。『假设 P(k) 成立』听起来像把要证的东西先当真，于是像循环论证。但看清楚你到底假设了什么：不是『对所有 n 成立』（那是结论），而是『在某一个位置 k 上成立』。你甚至没有断言这个位置真的存在，你只是在问：如果一块骨牌倒了，它后面那块会不会跟着倒？回答这个问题，不需要那块骨牌真的倒。归纳步骤生产的是一根箭头，不是一个事实。借走的是假设，交回来的是箭头，两者不是同一样东西——这就是它不循环的原因。
起点也不是走过场。假设你只证了箭头。看这个断言 Q(n)：前 n 个奇数之和等于 n²+1。它的归纳步骤照样成立——(k²+1) 加上第 k+1 个奇数 2k+1，正好等于 (k+1)²+1。整排骨牌之间的传递关系完好无损，只是没有一块倒下。Q(n) 对任何 n 都不成立，却通过了归纳步骤的检验。少了基例，你证明的只是『如果哪天成立，以后就一直成立』，而这个『哪天』可能永远不来。
反过来，只验起点、甚至多验几百个起点，也永远走不到无穷远处。真正把无穷压缩成有限的，是这两件事的配合：一个具体的落脚点，加一条能被无限复用的传递规则。
记 P(n) 为一个关于自然数 n 的命题：对每个具体的 n，P(n) 或真或假。P(n) 是陈述，不是数——『1+3+⋯+(2n−1)』是数，『1+3+⋯+(2n−1) = n²』才是 P(n)。
数学归纳法：设 n₀ 是起点（常取 1 或 0）。若
(i) 基例：P(n₀) 为真；
(ii) 归纳步骤：对每个整数 k ≥ n₀，蕴含式 P(k) ⇒ P(k+1) 为真，
则对一切整数 n ≥ n₀，P(n) 为真。
量词的位置是全部关键。(ii) 中的 k 被全称量化——『对每个 k』；而 P(k) 出现在蕴含式的左侧，是前提，不是被断言为真的事实。你要证的是那根 ⇒，不是箭头的两端。所以写下『假设 P(k) 成立』时，k 是一个任意但固定的值，这个『成立』的作用域仅限于本次推导内部。
P(k) 在推导中称为归纳假设。它合法，是因为当 P(k) 为假时蕴含式自动为真，你只需处理 P(k) 为真的那一支。
(i) 与 (ii) 相互独立，缺一不可：存在满足 (ii) 而 (i) 为假的命题（如 Q(n)），也存在满足 (i) 而 (ii) 为假的命题。
跟着做一遍
证明：对每个整数 n ≥ 1，前 n 个奇数之和等于 n²，即 1+3+5+⋯+(2n−1) = n²。先自己动笔写一遍，再对照下面的步骤。
- 写出 P(n)：1+3+⋯+(2n−1) = n²。确认它是一个命题，n 是其中的自由变量。
- 基例 P(1)：左边只有一项，2·1−1 = 1；右边 1² = 1。两边相等，基例成立。
- 声明归纳假设：固定某个整数 k ≥ 1，假设 P(k) 为真，即 1+3+⋯+(2k−1) = k²。只假设这一个 k，不假设所有 n。
- 写出待推目标 P(k+1)：1+3+⋯+(2k−1)+(2k+1) = (k+1)²。注意第 k+1 个奇数是 2(k+1)−1 = 2k+1。
- 从 P(k+1) 的左边出发，把前 k 项打包成一个方括号：[1+3+⋯+(2k−1)] + (2k+1)。
- 用归纳假设替换方括号：= k² + (2k+1)。这是整份证明中唯一用到假设的地方。
- 展开右边核对：(k+1)² = k²+2k+1，与上式逐项相同。于是 P(k) ⇒ P(k+1) 得证。
- 基例与归纳步骤都有了，结论成立。用 n=5 抽查：1+3+5+7+9 = 25 = 5²。
结果
1+3+⋯+(2n−1) = n² 对所有整数 n ≥ 1 成立。整个证明只做了两件有限的事：验证一个等式（n=1），以及完成一次代数变形（k²+2k+1 = (k+1)²）。把第 6 步的替换抽掉，推导会立刻卡死——归纳假设的全部作用就在那一行。