6. 归纳法与二项式定理

学习目标与准备

公式可能在几个例子中正确，之后却失败。本章区分证据与证明。你将写出具有整数定义域的命题，组织基础情形与归纳步骤，仅在允许处使用假设，并推导和应用二项式定理。第 5 章提供有限数列和代数恒等式；本章不假设概率论知识。

6.1 归纳法究竟证明什么

设 $P(n)$ 是关于整数 $n\ge n_0$ 的陈述，$n_0$ 固定。数学归纳法说明：

1. 证明基础情形 $P(n_0)$。
2. 对任意整数 $k\ge n_0$，假设 $P(k)$，并证明 $P(k+1)$。
3. 得出对每个整数 $n\ge n_0$ 都有 $P(n)$。

第 2 步的假设是归纳假设，它是条件性的，不是预先假设最终定理成立。基础情形启动链条，蕴含则将任意有效一环延伸到下一环。

可用非负整数的最小元素性质说明：若有反例，则存在最小反例 $m\ge n_0$。基础情形排除 $n_0$，于是 $m-1\ge n_0$ 不是反例，归纳步骤迫使 $P(m)$ 成立，矛盾。

对于任意整数起点 $n_0$，将指标平移为 $m-n_0\ge0$，即可用最小元素性质证明上面的最小反例步骤。

反过来，正整数上的普通归纳法蕴含最小元素性质。假设非空集合 $S\subseteq\{1,2,3,\ldots\}$ 没有最小元素。令 $P(n)$ 表示 $1,\ldots,n$ 均不属于 $S$。若 $1\in S$，它就是最小元素，故 $P(1)$ 成立。若 $P(k)$ 成立而 $k+1\in S$，则 $k+1$ 是 $S$ 的最小元素，矛盾。因此 $P(k)\Rightarrow P(k+1)$。归纳法给出每个正整数 $n$ 都满足 $P(n)$，于是 $S$ 为空，与其非空假设矛盾。所以每个非空正整数集合都有最小元素。用 $n\mapsto n-n_0+1$ 平移指标，即得任意整数起点 $n_0$ 的对应归纳版本。

不要在步骤中假设准备证明的命题对所有整数成立。只假设声明的 $P(k)$（或强归纳法中明确允许的先前情形），再推导下一情形。归纳法证明整数指标上的陈述，不自动涵盖所有实数。

例 1——边界移动的和。 对每个正整数 $n$，

$$1+2+\cdots+n=\frac{n(n+1)}2.$$

当 $n=1$，两边均为 $1$。假设等式对任意 $k\ge1$ 成立，则

$$1+\cdots+k+(k+1)=\frac{k(k+1)}2+(k+1) =\frac{(k+1)(k+2)}2,$$

恰是 $n=k+1$ 时所需公式。左边只增加一项，而不是无解释的新表达式。

6.2 选择陈述并使用假设

例 2——重复增加的递推式。 假设 $B_0=0$、$B_{n+1}=rB_n+c$，其中 $r,c$ 是固定实数。声称

$$B_n=c\sum_{j=0}^{n-1}r^j\quad(n\ge1).$$

基础情形 $n=1$ 给出 $B_1=c$。假设公式对 $k\ge1$ 成立，递推式给出

$$B_{k+1}=rc\sum_{j=0}^{k-1}r^j+c =c\left(1+\sum_{j=1}^{k}r^j\right)=c\sum_{j=0}^{k}r^j.$$

故命题对所有正整数成立。使用第 5 章的有限几何和，$r\ne1$ 时得到 $c(1-r^n)/(1-r)$，$r=1$ 时得到 $nc$。归纳证明本身没有除以 $1-r$，因此也覆盖例外公比。

例 3——整除性。 当 $n\ge1$，$7^n-1$ 被 $6$ 整除。在 $n=1$ 它等于 $6$。若对整数 $m$ 有 $7^k-1=6m$，则

$$7^{k+1}-1=7(7^k-1)+6=6(7m+1).$$

乘数 $7m+1$ 是整数，这证明整除性，而不只是观察表达式为偶数。

有时加强陈述有助于归纳。证明递推界时，较弱的目标可能没有提供传递到下一步所需信息。初等证明中，应先明确写出 $P(k+1)$，再确定递推式需要什么估计。不能以“模式显然继续”替代失败步骤。

6.3 不等式与乘数符号

对实数 $t\ge-1$ 和整数 $n\ge1$，Bernoulli 不等式为

$$(1+t)^n\ge1+nt.$$

$n=1$ 处显然取等。从 $k\ge1$ 出发，乘以 $1+t\ge0$ 保持所假设不等式的方向：

$$(1+t)^{k+1}\ge(1+kt)(1+t) =1+(k+1)t+kt^2\ge1+(k+1)t.$$

非负余项证明下一情形。乘数条件不可少；乘以负数会反转不等号。对 $t>0$、$n\ge2$，不等式严格，因为 $k=1$ 的步骤已经加入正数 $t^2$。

例 4——下界不等于精确值。 某假设量在 $10$ 个相等周期中每期增加 $2\%$。其乘数满足 $1.02^{10}\ge1+10(0.02)=1.2$，故增加至少 $20\%$，不恰好是 $20\%$。精确乘数由复合表达式给出。归纳无需小数近似即可证明可靠比较。

错误分析。 $2^n\ge n^2$ 在 $n=1,2$ 成立，却在 $n=3$ 失败，因为 $8<9$。正确归纳证明不可能覆盖所有 $k\ge1$。它对 $n\ge4$ 成立：在 $4$ 取等，且对 $k\ge4$，

$$2^{k+1}\ge2k^2\ge(k+1)^2,$$

因为 $2k^2-(k+1)^2=k^2-2k-1=(k-1)^2-2>0$。起始范围是定理的一部分。

6.4 二项式系数与 Pascal 恒等式

对整数 $n\ge0$、$0\le k\le n$，定义

$$\binom nk=\frac{n!}{k!(n-k)!},\qquad 0!=1.$$

它计算从 $n$ 个不同对象中选取 $k$ 个的方式：有 $n(n-1)\cdots(n-k+1)$ 个有序选择，每个无序选择出现 $k!$ 个顺序。特别地 $\binom n0=\binom nn=1$、$\binom nk=\binom n{n-k}$。

对 $1\le k\le n$，Pascal 恒等式为

$$\binom n{k-1}+\binom nk=\binom{n+1}k.$$

无需阶乘运算即可说明：在 $n+1$ 个对象中特别标记一个。$k$ 元选择要么包含它，此时其余 $k-1$ 个从 $n$ 个中选；要么不包含它，此时所有 $k$ 个从 $n$ 个中选。两种情况互斥且穷尽。也可将两个阶乘分式通分至 $k!(n+1-k)!$；分子因子之和为 $k+(n+1-k)=n+1$。

6.5 推导二项式定理

对非负整数 $n$ 和实数 $a,b$，

$$(a+b)^n=\sum_{k=0}^{n}\binom nk a^{n-k}b^k.$$

此多项式恒等式中，指数为零的幂代表常数因子 $1$，包括 $a=0$ 或 $b=0$ 时。这是多项式求值约定，不是声称每个极限表达式 $0^0$ 都有指定值。

归纳证明。 当 $n=0$，两边均为 $1$。假设公式对 $n$ 成立，乘以 $a+b$。一部分贡献 $\binom nk a^{n+1-k}b^k$；另一部分换指标后贡献 $\binom n{k-1}a^{n+1-k}b^k$。中间项用 Pascal 恒等式合并，两端保留 $a^{n+1}$ 和 $b^{n+1}$。结果恰是 $n+1$ 的公式。

也可直接理解：在 $n$ 个 $(a+b)$ 的乘积中，含 $k$ 个 $b$ 和 $n-k$ 个 $a$ 的项由选择哪 $k$ 个因子贡献 $b$ 而产生，共有 $\binom nk$ 种选择。这同时解释系数和指数。

整数条件很重要。例如 $(1+x)^{1/2}$ 不是两项多项式。无穷二项展开需要额外收敛理论，不是此处证明的有限定理。

例 5——只提取所需系数。 在 $(2x-3)^5$ 中，含 $x^3$ 的项使用 $k=2$ 个 $-3$：

$$\binom52(2x)^3(-3)^2=720x^3.$$

故系数为 $720$。负项平方，符号为正。

例 6——含倒数幂的系数。 在 $(x^2+1/x)^6$ 中（$x\ne0$），一般项为 $\binom6k x^{12-3k}$。常数项出现在 $12-3k=0$，故 $k=4$，常数项为 $\binom64=15$。这是 Laurent 表达式而非 $x$ 的多项式，但对每个非零 $x$，有限二项式定理适用于两个有定义的实数输入。

令 $a=b=1$ 得 $\sum_{k=0}^{n}\binom nk=2^n$。对 $n\ge1$，令 $a=1,b=-1$ 得 $\sum_{k=0}^{n}(-1)^k\binom nk=0$。后者排除 $n=0$，其和为 $1$。

6.6 分级练习

基础

1. 写出证明对所有整数 $n\ge3$ 成立所需的基础情形和归纳步骤。
2. 计算 $\binom62$ 和 $\binom64$，解释为什么相同。
3. 精确展开 $(x+2)^4$。

核心

4. 证明对每个正整数 $n$，$1+3+\cdots+(2n-1)=n^2$。
5. 证明对每个整数 $n\ge1$，$3^n-1$ 被 $2$ 整除。
6. 用归纳法证明 $1+2+4+\cdots+2^{n-1}=2^n-1$，不要引用几何和公式。
7. 求 $(3x-1)^5$ 中 $x^2$ 的系数。
8. 对 $x\ne0$，求 $(x^3-2/x)^8$ 的常数项。

综合

9. 学生声称任何 $n$ 个彩色计数物的集合只有一种颜色：“$n=1$ 成立；对 $(n+1)$ 个，分别去掉第一个和最后一个，两个 $n$ 元子集各自只有一种颜色，所以所有对象同色。”指出失败步骤。
10. 用有限二项式定理证明 $t\ge0$ 时 $(1+t)^5\ge1+5t+10t^2$。对每个 $-1\le t<0$ 同样成立吗？
11. 用归纳法证明 $\sum_{j=1}^{n}j^2=n(n+1)(2n+1)/6$。
12. 对 $n\ge1$，用选择论证证明 $\sum_{k=0}^{n}k\binom nk=n2^{n-1}$。

6.7 完整解答

1. 验证 $P(3)$。然后对任意整数 $k\ge3$，假设 $P(k)$ 并推导 $P(k+1)$。仅有 $1$ 处基础情形而缺少中间连接情形，不能自行从 $3$ 启动链条。
2. 两者均为 $6!/(2!4!)=15$。选择两个选中对象等价于选择四个被省略对象。
3. 系数为 $1,4,6,4,1$，故 $(x+2)^4=x^4+8x^3+24x^2+32x+16$。
4. 基础情形为 $1=1^2$。若前 $k$ 个奇数和为 $k^2$，加入下一个 $2k+1$ 得 $k^2+2k+1=(k+1)^2$。
5. $1$ 处 $3-1=2$。若 $3^k-1=2m$，则 $3^{k+1}-1=3(3^k-1)+2=2(3m+1)$，为偶整数。
6. $1$ 处 $1=2-1$。若到 $2^{k-1}$ 的和为 $2^k-1$，加入 $2^k$ 得 $2^{k+1}-1$。
7. 恰选两个 $3x$ 和三个 $-1$，系数为 $\binom52 3^2(-1)^3=-90$。
8. 一般项为 $\binom8k(-2)^k x^{24-4k}$。指数在 $k=6$ 时为零，得到 $\binom86(-2)^6=28(64)=1792$。
9. 从一个推到两个对象时，两个单元素子集没有共同成员，没有共享对象使颜色相等。所提步骤恰在第一环失败；后续重叠不能修复它。
10. 被省略部分为 $10t^3+5t^4+t^5=t^3(10+5t+t^2)$，在 $t\ge0$ 时非负。对 $-1\le t<0$，$t^3<0$ 且 $10+5t+t^2>0$，故所提不等式严格反向；例如 $t=-1$ 时它会写成 $0\ge6$。
11. $1$ 处公式给出 $1$。在所假设和上加 $(k+1)^2$，得 $k(k+1)(2k+1)/6+(k+1)^2=(k+1)(2k^2+7k+6)/6=(k+1)(k+2)(2k+3)/6$，恰是 $k+1$ 情形。
12. 计数数对 $(S,s)$，其中 $S$ 是 $n$ 元集的子集，$s\in S$ 被标记。按子集大小计数有 $\sum_k k\binom nk$ 种。也可先以 $n$ 种方式选 $s$，再独立选择其他 $n-1$ 个元素中哪些属于 $S$，有 $2^{n-1}$ 种。两种计数相等。

总结与迁移

归纳证明要声明整数范围、起始情形，以及在每个所需环节有效的蕴含。整除证明展示整数倍；不等式证明论证每个乘数的符号。二项式系数计算选择数，Pascal 恒等式合并相邻系数，有限二项式定理可由乘法或选择推导。提取系数先是指数问题，再是算术问题。