8. 计数、归纳法与二项式定理

设 $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$ 的对应归纳版本。

学习目标与定义

计算有序与无序选择的数量，证明有限二项式定理，并将系数与恒等式联系起来。对正整数，令 $n! =1\cdot2\cdots n$，并定义 $0!=1$。对整数 $0\le k\le n$，二项式系数

$$\binom nk=\frac{n!}{k!(n-k)!}$$

计数一个 $n$ 元集合的 $k$ 元子集。理由是：先按次序选出 $k$ 个不同元素，有 $n(n-1)\cdots(n-k+1)$ 种方法；每个子集恰好出现 $k!$ 种次序。对 $0\le k\le n$ 以外的整数，定义 $\binom nk=0$。

乘法原理在每阶段都有所述数目的后续选择时，将各阶段选择数相乘。加法原理将互斥方案的数量相加。若方案重叠，相加会重复计数；因此有限集合的容斥从 $|A\cup B|=|A|+|B|-|A\cap B|$ 开始。

定理：帕斯卡恒等式与二项式定理

对整数 $n\ge0$，

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

该多项式恒等式对所有实数或复数 $a,b$ 成立。

证明。 从一个含指定元素的集合中选 $k$ 个元素，可分为包含该元素（从其余 $n$ 个中选 $k-1$ 个）和不包含该元素（从其余 $n$ 个中选 $k$ 个）两类。这两类互斥且穷尽，故证明帕斯卡恒等式，包括按零约定处理的边界情况。二项式定理在 $n=0$ 成立。假设它在 $n$ 成立，乘以 $a+b$；$a^{n+1-k}b^k$ 的系数有 $\binom nk$ 和 $\binom n{k-1}$ 两部分，由帕斯卡恒等式相加为 $\binom{n+1}k$。这证明归纳步骤，也证明所有非负整数情况。

定理是有限的。若将 $n$ 换成非整数，得到的是无穷二项式级数，需要本归纳证明未提供的收敛定理。

例题

含负项的系数。 在 $(2x-1)^5$ 中，$x^3$ 的系数使用三个 $2x$ 和两个 $-1$，所以是 $\binom53 2^3(-1)^2=80$。先数出 $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$，故偶数大小与奇数大小的子集一样多。组合证明可切换一个固定元素的包含状态，将每个偶数子集与一个奇数子集配对。

无序选择。 从七人中选三人委员会，有 $\binom73=35$ 种方法。若分别指定主席、秘书和司库，则有 $7\cdot6\cdot5=210$ 种，因为职位区分了不同顺序。

分层练习

1. 基础。 计算 $\binom82$ 并解释它计数什么。
2. 核心。 求 $(1-3x)^6$ 中 $x^4$ 的系数。
3. 核心。 从一副标准的 52 张牌中选五张，恰好含两张 A 的手牌有多少种？说明为何各因子相乘。
4. 证明。 对 $n\ge1$，通过计数一个子集及其中一个指定成员，证明 $\sum_{k=0}^n k\binom nk=n2^{n-1}$。

详解

1. $\binom82=8\cdot7/2=28$，它计数八元集合中不同元素组成的无序对。
2. 选四个 $-3x$ 和两个 $1$，系数为 $\binom64(-3)^4=15\cdot81=1215$。
3. 从四张 A 中选两张，从 48 张非 A 中选三张，得到 $\binom42\binom{48}3$。每副手牌都唯一分成 A 和非 A 两部分；一部分的每个允许选择都可以与另一部分的每个允许选择配对。因此可相乘，不需要假设概率模型。
4. 对每个大小 $k$，有 $\binom nk$ 个子集及 $k$ 种指定成员选择，得到左边。另一种方法是先用 $n$ 种方法选择指定成员，再从剩下 $n-1$ 个元素中任选子集，有 $2^{n-1}$ 种。两边计数完全相同的对子，故恒等式成立。

总结与术语

排列是有序选择；组合是无序选择。归纳法证明初始情形和每一步到下一步的蕴含，而不是只检验几个例子。系数是乘以指定幂的标量。有限二项式展开来自精确计数或归纳；任何无穷推广都需要另行分析收敛和余项。