数学归纳法与递推证明

第一数学归纳法

设 $P(n)$ 是关于整数 $n\ge n_0$ 的命题。要证明所有这些命题均成立，可完成两步：

1. 归纳起点： 证明 $P(n_0)$ 成立。
2. 归纳过渡： 对任意整数 $k\ge n_0$，在 $P(k)$ 成立的假设下，证明 $P(k+1)$ 成立。

第二步的假设只涉及第 $k$ 项，不能先把第 $k+1$ 项的待证结论当成已知。起点也不必是 $1$，应与命题的实际范围相符。

该方法依据自然数的归纳原理：一个包含起点、且包含每个已有整数的后继的整数集合，必包含从起点开始的所有整数。也可用最小数原理说明：若存在不成立的情形，取最小的失败下标 $m$。起点已成立，所以 $m>n_0$；由最小性，$P(m-1)$ 成立，归纳过渡便推出 $P(m)$ 成立，矛盾。

第二数学归纳法（强归纳法）

仍先证明 $P(n_0)$，但归纳过渡允许假设

全部成立，再推出 $P(k+1)$。这适合新情形依赖多个较早情形、而非仅依赖前一项的问题。

与第一归纳法的关系。 定义 $Q(k)$ 为“$P(n_0),\ldots,P(k)$ 全部成立”。强归纳的起点给出 $Q(n_0)$；过渡步骤给出 $Q(k)\Rightarrow Q(k+1)$。对 $Q$ 使用第一归纳法，就得到所有 $P(n)$。因此强归纳并未增加未经证明的条件，而是对整个已完成的前缀归纳。

若递推使用前两项，通常需先验证两个初值，随后从第二个下标开始归纳。初值的数量由实际过渡所需的最早下标决定。

跳跃归纳、反向归纳与交替归纳

跳跃归纳

设步长 $l\ge1$。若已证明连续 $l$ 个起点

并对所有 $k\ge n_0$ 证明 $P(k)\Rightarrow P(k+l)$，则 $P(n)$ 对全部 $n\ge n_0$ 成立。

证明。 每个 $n\ge n_0$ 唯一写成 $n=n_0+r+ql$，其中 $0\le r<l$，$q\ge0$ 为整数。从对应起点 $n_0+r$ 连续使用 $q$ 次过渡即可。只验证一个起点一般只能覆盖一个剩余类。

反向归纳

若 $P(n)$ 对无穷多个正整数 $n$ 成立，并且对每个正整数 $k$ 都能由 $P(k+1)$ 推出 $P(k)$，则 $P(n)$ 对所有正整数成立。

证明。 任取正整数 $m$。无穷多个正整数构成的集合不可能有有限上界，因此可取 $N\ge m$ 使 $P(N)$ 成立。连续向下推导，便得到 $P(m)$。关键条件是已经成立的下标任意大；只知道某个有限下标成立，只能推到它之前。

均值不等式中“先证 $2^k$ 项，再向下补齐任意项数”的证明就是这种思路，详见均值不等式。

交替归纳（螺旋归纳）

若有两组命题 $P(n),Q(n)$，已知 $P(n_0)$，且对所有 $k\ge n_0$ 有

则两组命题均成立。

证明。 将两次推导合起来，得到 $P(k)\Rightarrow P(k+1)$，先证明所有 $P(k)$；再用第一条推导得到相应的 $Q(k)$。这里是跨下标的推进，不能把同一下标下的 $P(k)\Rightarrow Q(k)\Rightarrow P(k)$ 当作证明。

加强命题与递推证明的选择

有时待证结论 $P(k)$ 提供的信息不足以推出 $P(k+1)$。可以寻找更强、但更适合递推的命题 $Q(k)$，满足 $Q(k)\Rightarrow P(k)$，然后证明 $Q(n_0)$ 和 $Q(k)\Rightarrow Q(k+1)$。完成后，原命题随之成立。

加强的内容通常来自下一步运算需要的条件，例如同时保留上下界、符号、单调性或两个相邻量之间的关系。选择时应先写出下一步要估计的表达式，再检查哪些信息在过渡中缺失，避免任意猜一个更复杂的结论。

对于递推数列，可按以下顺序判断：

1. 若递推能直接求出通项，先求通项，再研究目标性质。
2. 若通项复杂或不可得，检查目标性质能否从前项传到后项，如正性、有界性或整除以外的代数关系。
3. 若只靠前一项不够，考虑强归纳或同步证明辅助性质。
4. 对不等式过渡，逐次检查代入方向、乘除量的正负及等号条件。

观察若干小规模值可以帮助猜测 $Q(n)$，但不能替代对任意下标的归纳过渡。