普通归纳：一排学生与两条规定
Ordinary Induction教授带着一袋糖进了教室，让学生按 0 号起排队，宣布两条规则：① 队首（0 号）有糖；② 有糖的人，下一个也有糖。你是 17 号——糖归你了：0 号有糖（规则①），于是 1 号有（规则②），于是 2 号有……规则②用了 17 次，糖到你手。而且不管队伍多长，人人都跑不掉。
设 P 是非负整数上的谓词。若
• P(0) 为真，且
• 对所有非负整数 n，P(n) 蕴含 P(n+1)，
则对所有非负整数 m，P(m) 为真。
它的第一个正式战果是把第 2 章良序版的求和公式再证一遍（定理 5.1.1）——基例 P(0) 是空和约定，归纳步给等式两边同加 (n+1)。同一个定理，两种证明格式。
5.1.3五步模板
① 宣布"用归纳法"；② 定义谓词 P(n)（归纳假设，最关键的一步）；③ 证基例 P(0)；④ 证归纳步 P(n) ⇒ P(n+1)（假设 P(n) 真，推出 P(n+1) 真，必须对每个 n 成立）；⑤ 调用归纳原理收尾。
骨架又来了——上一章搭过良序版，这次换归纳版：
同色马悬案：归纳链断在哪一环？
A Faulty Induction Proof任意 n ≥ 1 匹马，全部同色。
归纳假设、基例 P(1) 都规规矩矩——问题藏在归纳步的一句"显然"里。老规矩，亲手指出第一次犯规：
强归纳
Strong Induction若 P(0) 为真，且 P(0), P(1), …, P(n) 全体蕴含 P(n+1)（对所有 n），则 P(m) 对所有非负整数 m 为真。
唯一的变化：归纳步允许假设 P(0)…P(n) 全部为真，而不只 P(n)。
什么时候非用强归纳不可？当 P(n+1) 依赖的不只是 P(n)——比如 Fibonacci 数 F(n+1) 依赖 F(n) 和 F(n−1) 两代（原书用它证"F(n) 是偶 ⟺ F(n+3) 是偶"，基例要验证 n=0 和 n=1 两个）；又比如素分解——n+1 拆成哪两个因子事先不知道，只知道它们都比 n+1 小。做完下面四道场景判断，手感就来了：
堆叠游戏：策略无关的得分
The Stacking Gamen 个箱子摞成一摞。每一步把一摞拆成两个非空子摞，得分为两摞高度之积 a×b；拆到全为单箱时游戏结束。定理 5.2.1 断言一个惊人的事实：无论你用什么策略，总分恒为 n(n−1)/2。强归纳一步证明（第一步拆成 a+b 块，总分 = ab + a(a−1)/2 + b(b−1)/2 = n(n−1)/2，由归纳假设 P(a)、P(b)）。空口无凭，跑两把试试——换着策略跑：
5.2.4顺手的实战：Inductia 换零钱
Inductia 国只有 3Sg 和 5Sg 两种硬币，但 ≥ 8Sg 的任何金额都找得开。强归纳：n+1 ≥ 11 时，先找 (n+1)−3 ≥ 8 的零钱（归纳假设），再加一枚 3Sg——只剩基例 8=3+5、9=3+3+3、10=5+5 要手工验证。玩一下验证机：
强归纳 vs. 普通归纳 vs. 良序
Three Formats of the Same Reasoning强归纳看着比普通归纳"强"——能假设的更多嘛。但原书捅破：三者是同一推理的三种排版。任何强归纳证明都能机械改写成普通归纳（给归纳假设套一个全称量词），任何良序证明也能自动改写成归纳证明（和被改回）。第 2 章的求和公式良序版与本章的归纳版，就是同一个数学内容换了字体。
习题实战：下标变量与归纳步
5.3.2 & Practice, Playable5.3.2 的下标变量是最容易绊倒新手的写作细节；归纳步则用经典奇数和亲手走一遍。
终局自测
Final Check六题，覆盖全章。
彩蛋与课后挑战
Easter Eggs & ProblemsFibonacci 的奇偶心跳（原书 5.2.2，式 5.4）
0, 1, 1, 2, 3, 5, 8, 13, 21…… 奇偶模式"偶偶奇？不——偶奇奇"循环，周期恰为 3：F(n) 是偶 ⟺ F(n+3) 是偶。强归纳双基例（n=0、n=1）+ 关键引理"m+k 为偶 ⟺ m、k 同奇偶"。原书还留了课后钩子：F(n−1)·F(n+1) − F(n)² = (−1)ⁿ（习题 5.8，卡西尼恒等式）。
Geherhy 的邪门瓦片（原书习题 5.2）
建筑师 Ghery 后来又想用一种"错位 L 瓦片"铺庭院，还配了一个看似与正文 5.1.5 一模一样的归纳证明。找出它崩掉的那一步——提示：正文证明里三个临时 Bill 恰好拼成一块 L 瓦片；错位瓦片可没有这么听话。"强化假设"必须是真的假设，否则归纳机器空转。
又一个 bogus：2+3+4+⋯+n = n(n+1)/2（原书习题 5.7）
这个"证明"连归纳步都挑不出毛病——问题出在基例：P(0) 说"2+3+⋯+0 = 0"。但"从 2 加到 0"根本不是合法的省略号用法（空和约定只救 Σ 从 1 起的和）。省略号的起止语义，第 2 章就警告过你。
餐巾纸上的归纳（原书 5.1.5 节末尾的故事）
"每个平面图都是 5-可选择的"这个猜想让数学家折腾了二十来年。1994 年 Carsten Thomassen 给出的归纳证明简单到能写在餐巾纸上——关键同样是找到那个绝妙的归纳假设。找假设可以要二十年，写下来只要五分钟：归纳法的力气都花在刀刃上。