选择恰当的归纳对象

一句话

命题里有 $m,n$ 两个（或更多）变量时，把所有情形 $P(m,n)$ 摆成一张格子表。证明某一格时，归纳一步会用到另外几格——用到谁，就得让归纳假设覆盖谁。可以选的“归纳对象”有：

• 对 $m$ 归纳（$n$ 任意）：假设所有 $m^{\prime }<m$ 的格子成立，覆盖的是左边的整列；
• 对 $n$ 归纳（$m$ 任意）：覆盖的是下面的整行；
• 对 $m+n$ 归纳：覆盖的是左下方的斜三角；
• 双重归纳（先 $m$ 后 $n$）：左边的整列，再加上本列下面的格子。

此外，“归纳对象”也可以不是题目里写出的某个字母：变量的个数、两数之和、面积……谁在每一步里真的变小，就对谁归纳。

第 1 站 · 计数：走格子

上面的 ${\mathrm{C}}_{m+n}^m$ 本身就是一个很好的例子：对 $m+n$ 归纳。起点是 $m=0$ 或 $n=0$ 的边（只有一种走法，${\mathrm{C}}_n^0={\mathrm{C}}_m^m=1$）；归纳一步就是杨辉三角的递推 ${\mathrm{C}}_k^m={\mathrm{C}}_{k-1}^{m-1}+{\mathrm{C}}_{k-1}^m$。这里的“$m+n$”正是走的总步数——归纳对象往往是问题里一个有意义的量。

第 2 站 · 不等式：对变量的个数归纳

例 $x_1,\dots ,x_n\in (0,1)$，证明 $(1-x_1)(1-x_2)\cdots (1-x_n)\ge 1-(x_1+x_2+\cdots +x_n)$。

这里没有第二个字母，可是有两样东西在变：变量的个数 $n$ 和变量的取值。取值是连续的，没法归纳；个数可以。

第 3 站 · 数论：对两数之和归纳

例 正整数 $m,n$ 的最大公约数 $d$ 可以写成 $d=mx+ny$（$x,y$ 是整数）。

两种选法都对：每一步让 $m+n$ 变小，或者让较小的那个数变小。哪个量每一步都严格变小，哪个量就能当归纳对象。

练一练