数学归纳法

解题套路

要证命题 $P(n)$ 对一切 $n\geq n_{0}$ 成立：

1. 起点（奠基）。验证 $P(n_{0})$ 成立。这一步通常只是代一个数，但不能省。
2. 递推（归纳步）。设 $P(k)$ 成立（$k\geq n_{0}$ 任意），据此推出 $P(k+1)$ 成立。
3. 收口。两条都有，则 $P(n)$ 对一切 $n\geq n_{0}$ 成立。

第 2 步里那句「设 $P(k)$ 成立」叫归纳假设。它不是「假定结论成立」—— 它假定的是某一个下标处成立，要证的是下一个下标处成立； 真正被证明的是一条箭头 $P(k)\Rightarrow P(k+1)$，而不是 $P$ 本身。

归纳步到底在证什么

把 $P(n_{0}),P(n_{0}+1),P(n_{0}+2),\dots$ 想成一排多米诺骨牌：

• 起点那一步 = 推倒第一张；
• 归纳步 = 保证「每一张倒下都会碰倒下一张」。

缺哪一条都不行。只有起点，第二张不一定倒；只有归纳步，可能一张都没倒 （$P(n)$ 取「$n=n+1$」时归纳步照样成立，可它从来不真）。

三条必须守的规矩

1. 归纳假设一定要真的用上。 归纳步里如果一次都没引用 $P(k)$， 那说明你其实是直接证明了 $P(k+1)$——那就不必写成归纳法，写成直接证明更清楚； 反过来，若怎么也用不上，多半是假设开得不对，见第 3 条。
2. 起点要选对，且要验到位。 结论里若出现 $n-1$、$\frac{1}{n-1}$ 这类，起点可能得从 $2$ 起； 有的递推每一步跨两格（$P(k),P(k+1)\Rightarrow P(k+2)$），那就要验两个起点。
3. 假设太弱时要主动加强。 有时 $P(k)$ 推不出 $P(k+1)$， 但一个更强的命题 $Q(k)$（$Q\Rightarrow P$）反而能推出 $Q(k+1)$—— 这叫加强归纳假设。看起来是把任务变难了，实际是把手上的弹药变多了。 要证双边界的题里，这一条常表现为「上下两条界必须一起归纳」， 单证一边会发现另一边的信息不够用。

什么时候它几乎是唯一的路

• 通项求不出来的递推。$a_{n+1}=F(a_{n})$ 只要 $F$ 稍微复杂一点就没有封闭式， 但「$a_{n}$ 落在哪个区间」往往可以归纳。这时归纳步就是「把区间代进 $F$ 再看落到哪」， 需要先知道 $F$ 在那一段上的单调性。
• 结论里带着 $n$ 的和式或积式。$\sum$、$\prod$ 加一项正好就是从 $k$ 到 $k+1$， 归纳步天然对上。
• 答案是猜出来的。先算几项猜一个封闭式，再用归纳法把「前几个对」升级成「每一个都对」。

常见的坏味道

• 把归纳步写成了「因为 $P(k)$ 成立，所以 $P(k+1)$ 也成立」。 这句话什么也没证。 归纳步必须是一段真正的推导，从 $P(k)$ 的式子出发算到 $P(k+1)$ 的式子。
• 归纳步只对足够大的 $k$ 成立，却没交代。 推导中间出现「因为 $k\geq 2$」这类条件时， 起点就得跟着挪到 $2$，并把 $n=1$ 单独验一遍。
• 区间型结论忘了验「新区间还在定义域里」。 用 $F$ 的单调性把 $a_{k}$ 的界搬成 $a_{k+1}$ 的界之前， 必须先确认 $a_{k}$ 的那两条界都落在 $F$ 的单调区间内，否则搬运的方向可能是反的。