二项式定理

对 $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$,归纳完成。