递归式

猜测验证：看数列 1, 3, 7, 15, 31, 63 猜 Tₙ = 2ⁿ−1，再用归纳一锤定音（命题 22.1.1）——递归式与归纳证明结构天然同构：基例对第一行、归纳步对第二行。上界陷阱（22.1.1）：想证更"漂亮"的 Tₙ ≤ 2ⁿ？归纳在第 2·2ⁿ⁻¹ + 1 = 2ⁿ+1 ⋠ 2ⁿ 处当场翻车（书里标红 "Uh-oh!"）——弱假设撑不起弱结论，归纳常常需要更强的假设。

代入法（plug-and-chug）三步走：① 反复"代入-整理"直到出现模式（别过度化简！）；② 再做一轮验证模式（k → k+1 时公式形状不变，等于顺手完成了归纳）；③ 取 k = n−1 用已知的首项收尾。

对半拆、各自排好、线性归并。n 为 2 的幂时最大比较次数满足：

猜不好（0, 1, 5, 17, 49 看不出规律），代入法一锤定音。为什么归并只要 n−1 次？每出一个人至少比一次、最后一人免费——n 个数 n−1 次。

爬 n 阶楼梯，每次上一阶或跳两阶，几种爬法？f(n) = f(n−1) + f(n−2)——Fibonacci（书中边界 f(0)=f(1)=1，所以 f(4)=5）。解法六百年没人找到，如今一小时学会：猜 f(n)=xⁿ，除出特征方程 x² = x + 1，两根 φ 与 ψ；线性组合定理（22.3.1）说解空间是二维平面；两个边界条件解出 s, t——Binet 公式再临（第 16 章的它又回来了）。

汉诺塔的 +1 不是齐次项——五步收拾它：① 令 g(n)=0 得齐次递归求根；② 写齐次解；③ 猜一个特解（按 g(n) 的形状猜：常数→常数不行就升阶多项式；指数→c·3ⁿ 不行就乘 n 再试）；④ 齐次 + 特解 = 通解；⑤ 边界条件解常数。书中变体：大盘耗时正比于盘号，f(n)=2f(n−1)+n → f(n) = 2·2ⁿ − n − 2——和尚们要多干一倍的活。

Merge Sort 的 T(n) = 2T(n/2) + n − 1 不是线性的（回头找 T(n/2)，半路远亲）。分治递归 T(n) = ΣaᵢT(bᵢn) + g(n) 有流水线配方——Akra-Bazzi 公式（式 22.2）：先解 Σaᵢbᵢ^p = 1 定 p，再积一次分：

Merge Sort：2·(1/2)^p = 1 → p=1；∫(u−1)/u² du = ln u → Θ(n log n)。吓人版 T(n)=2T(n/2)+(8/9)T(3n/4)+n²：p=2，积出 Θ(n² log n)。另一个惊喜：边界条件完全不影响结果——Tₙ = Θ(n log n) 对任何 T₁ 都成立。

从第 1 章"什么是证明"到这里，全书的暗线其实只有一条：把大问题化小，直到基例出现——归纳证明、递归算法、递归式求解，是同一个思想的三副面孔。现在 22 章全部装配完毕：命题与量词是语法，集合与关系是名词，归纳与良序是引擎，数论给了你 RSA，图论给了你网络与平面，计数给了你扑克与魔术，概率给了你赌场与 Google，而递归式把它们全部串成闭环（谁还记得第 16 章已经解过一次汉诺塔？）。

原书到这里就停了。剩下的路——算法、复杂度、机器学习——用的全是这 22 章的语言。祝旅途愉快，常回来看看这些还能玩的装置。

终章核查题：给定递归式与候选闭式，代入前 6 项判定真假。

六题，覆盖全章——也是全书的最后一场考试。