二项式定理

展开 $(a+b)(a+b)\cdots(a+b)$(共 $n$ 个因子)就是从每个因子中选取 $a$ 或 $b$ 再相乘;$a^{n-k}b^k$ 的系数正是从 $n$ 个因子中选出 $k$ 个取 $b$ 的方法数,也就是 $\binom{n}{k}$。

对 $n$ 用归纳法证明。基础情形 $n=1$:$(a+b)^1=a+b=\binom{1}{0}a+\binom{1}{1}b$,由于 $\binom{1}{0}=\binom{1}{1}=1$,与公式相符。

归纳步骤:假设对某个 $n$ 公式成立,即 $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$。两边乘以 $(a+b)$:$(a+b)^{n+1}=\sum_{k=0}^n\binom{n}{k}a^{n+1-k}b^k+\sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1}$。

对第二个和以 $j=k+1$ 重新编号,再把两个和中 $a^{n+1-j}b^j$ 的系数合并,对每个从 $0$ 到 $n+1$ 的 $j$ 得到 $\binom{n}{j}+\binom{n}{j-1}$(约定 $\binom{n}{-1}=\binom{n}{n+1}=0$)。

由帕斯卡法则 $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$,此和等于 $\binom{n+1}{j}$,于是 $(a+b)^{n+1}=\sum_{j=0}^{n+1}\binom{n+1}{j}a^{n+1-j}b^j$,归纳完成。

在二项定理中令 $a$ 与 $b$ 都等于 $1$,每一项 $a^{n-k}b^k$ 都变成 $1$,于是整个和就只是在数项数。

把 $a=1,\ b=1$ 代入二项定理 $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$:左边变为 $(1+1)^n=2^n$,右边由于 $1$ 的任意次幂都是 $1$ 而变为 $\sum_{k=0}^n\binom{n}{k}1^{n-k}1^k=\sum_{k=0}^n\binom{n}{k}$。

令两边相等即得 $2^n=\sum_{k=0}^n\binom{n}{k}$。

这个恒等式还有直接的组合意义:$\binom{n}{k}$ 计算一个含 $n$ 个元素的集合 $S$ 中含 $k$ 个元素的子集数,因此 $\sum_{k=0}^n\binom{n}{k}$ 计算 $S$ 的所有大小的子集,也就是整个幂集,由于 $n$ 个元素中每个都独立地属于或不属于某子集,其元素个数恰为 $2^n$。