归纳法的步长、加强命题与双指标形式

归纳的核心是让每个待证下标都能从已证明的起点到达。变式改变的是下标之间的连接方式。

按依赖关系选择归纳方式

归纳方式取决于下一步实际需要哪些已知情形。下表用于选择，完整条件及证明分别见所链章节。

推理依赖	选择与起点要求
第 $k+1$ 项只需要第 $k$ 项	普通归纳：一个有效起点，逐项前进。
第 $k+1$ 项依赖多个更早下标	强归纳：可使用已证明的整个前缀，起点须覆盖最早依赖。
每次下标增加固定正整数 $h$	步长归纳：验证覆盖所有所需余类的起点。
已在任意大的下标成立，且能逐项倒推	反向归纳：先找到不小于目标的已知下标，再有限次倒推。
两组估计交替推动下一下标	交替归纳：两个推导必须形成跨下标的前进。
结论有两个非负整数指标	双指标归纳：找到严格下降的总指标，验证整条必要边界。
原结论不足以完成下一步	加强命题：加入在递推中可保持、且足以推出原结论的辅助信息。

同一下标下的两个命题互相推出，至多说明它们等价；如果没有已成立的起点和推进步骤，不能据此断言二者成立。有限次试算也只能验证那些下标，不能代替任意下标的推理。

固定步长需要覆盖所有余类

若只证明 $P(k)\Rightarrow P(k+h)$ ，其中 $h$ 为正整数，那么要得到全部 $n\ge n_0$ 的结论，须先证明 $P(n_0),\ldots,P(n_0+h-1)$ 。任意 $n\ge n_0$ 都能唯一写成 $n_0+r+qh$ ，其中 $0\le r<h$ ，故可从相应起点走 $q$ 步。

例如二步递推只从 $n=1$ 出发，会覆盖奇数下标而漏掉偶数。若命题本来只要求奇数下标，则只设一个奇数起点正好足够。

倒推归纳与均值不等式

若 $P(n)$ 在一列无上界的整数下标上成立，且对每个 $k\ge n_0$ 有 $P(k+1)\Rightarrow P(k)$ ，则所有 $n\ge n_0$ 均成立。给定 $n$ ，先取一个不小于 $n$ 的已知下标，再有限次倒推。

例如二元均值不等式可推出 $2^j$ 元均值不等式：将 $2m$ 个正数分成两组，各组使用 $m$ 元情形，再对两组均值用二元情形。反过来，若已知 $m+1$ 元情形，给 $m$ 个正数 $a_i$ 添入其算术平均 $A$ ，得到

A^{m+1}\ge a_1\cdots a_m A.

因 $A>0$ ，约去 $A$ 即得 $m$ 元情形。二的幂无上界，所以得到任意元数的均值不等式；等号沿推导追踪，要求原各数相等。

只知道一个固定大下标成立，倒推只能覆盖它以下的有限范围。

交替归纳：把关联命题一起证明

若有 $P(n_0)$ ，并且对所有 $k\ge n_0$ ，

P(k)\Rightarrow Q(k),\qquad Q(k)\Rightarrow P(k+1),

则两组命题都成立。逻辑链为 $P(n_0),Q(n_0),P(n_0+1),Q(n_0+1),\ldots$ 。

例如 $u_1=1$ ，且 $u_{n+1}=2-u_n/2$ 。取 $P(n):1\le u_n\le3/2$ ，取 $Q(n):1/2\le u_n/2\le3/4$ 。前者推出后者，后者给出 $5/4\le u_{n+1}\le3/2$ ，从而推出下一步的 $P$ 。这里中间命题较简单，但展示了如何让伴随估计封闭递推。

双指标归纳与对角线次序

设 $P(n,m)$ 对非负整数 $n,m$ 定义。若两条边界 $P(0,m)$ 、 $P(n,0)$ 均成立，且在 $n,m\ge1$ 时有

P(n-1,m)\text{ 与 }P(n,m-1)\Rightarrow P(n,m),

则全部成立。证明可对 $n+m$ 归纳：两个前驱的指标和都少 $1$ 。

这一形式适合满足 $A_{n,m}=A_{n-1,m}+A_{n,m-1}$ 的二维表。边界不能只查 $(0,0)$ ；整条横边、竖边共同决定内部各格。

加强命题以保留下一步所需信息

设 $u_1=1,u_{n+1}=\sqrt{2+u_n}$ ，若只想证明 $u_n<2$ ，归纳仍须确保开方有意义。可同时证明

1\le u_n<2.

起点成立；该区间经映射 $x\mapsto\sqrt{2+x}$ 后仍落在自身，故归纳闭合。进一步在同一区间有 $(2-u_n)(u_n+1)>0$ ，从而 $u_{n+1}>u_n$ 。

加强应提供具体可用的信息，例如正性、区间、误差方向或辅助恒等式；不能只把结论写得更复杂。

关联阅读