二项式定理学习笔记

· · 算法·理论

基本定理

$$\left(x+y\right)^n=\sum_{k=0}^n\dbinom{n}{k}x^{n-k}y^k$$ 其中，二项式系数的定义为 $$\dbinom{n}{m}=\frac{n!}{m!\left(n-m\right)!}$$ ## 推导过程 先考虑简单情况： $$\left(x+y\right)^3=\left(x+y\right)\cdot\left(x+y\right)\cdot\left(x+y\right)=x^3+3x^2y+3xy^2+y^3$$ 将括号拆开的方法是这样的：在每个括号里选一个数，将他们相乘，再将所得的结果与其他选法选出来的结果相加，即为答案。 也就是说，上述式子的结果，就是有含 $x^3,x^2y,xy^2,y^3$ 的项构成的。 接下来考虑系数，由于在三个括号中，选 $0$ 个 $x$ 有 $\dbinom{3}{0}$ 种情况，选 $1$ 个 $x$ 有 $\dbinom{3}{1}$ 种情况，选 $2$ 个 $x$ 有 $\dbinom{3}{2}$ 种情况，选 $3$ 个 $x$ 有 $\dbinom{3}{3}$ 种情况，所以 $$\left(x+y\right)^n=\sum_{k=0}^n\dbinom{n}{k}x^{n-k}y^k$$ ## 证明 此处使用数学归纳法。 显然，当 $n=1$ 时猜想成立。考虑 $n=m$ 时猜想成立，则当 $n=m+1$ 时有 $$ \begin{aligned} \left(x+y\right)^{m+1}&=\left(x+y\right)\cdot\left(x+y\right)^m \\ &=\left(x+y\right)\cdot\sum_{k=0}^m\dbinom{m}{k}x^{m-k}y^k \\ &=\sum_{k=0}^m\dbinom{m}{k}x^{m-k+1}y^k+\sum_{k=0}^m\dbinom{m}{k}x^{m-k}y^{k+1} \\ &=\sum_{k=0}^m\dbinom{m}{k}x^{m-k+1}y^k+\sum_{k=1}^{m+1}\dbinom{m}{k-1}x^{m-k+1}y^{k} \\ &=x^{m+1}+y^{m+1}+\sum_{k=1}^m\dbinom{m}{k}x^{m-k+1}y^k+\sum_{k=1}^{m}\dbinom{m}{k-1}x^{m-k+1}y^{k} \\ &=x^{m+1}+y^{m+1}+\sum_{k=1}^m\left(\dbinom{m}{k}+\dbinom{m}{k-1}\right)x^{m-k+1}y^k. \end{aligned} $$ 根据 $\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$，可得 $$\left(x+y\right)^{m+1}=x^{m+1}+y^{m+1}+\sum_{k=1}^m\dbinom{m+1}{k}x^{m-k+1}y^k=\sum_{k=0}^{m+1}\dbinom{m+1}{k}x^{m-k+1}y^k.$$ 由此归纳，等式得到证明。 ## 例 1 证明组合恒等式 $$\sum_{k=0}^n\dbinom{n}{k}=2^n$$ **证明**  根据二项式定理 $$\left(x+y\right)^n=\sum_{k=0}^n\dbinom{n}{k}x^{n-k}y^k\left(n\in\mathbb{N}\right)$$ 令 $x=y=1$，则有 $$\sum_{k=0}^n\dbinom{n}{k}=2^n$$ $$\quad$$ ## 例 2 证明组合恒等式 $$\sum_{k=0}^n\dbinom{n}{k}^2=\dbinom{2n}{n}$$ **证明**  对于等式 $\left(x+1\right)^n\cdot\left(x+1\right)^n=\left(x+1\right)^{2n}$ 展开可得 $$ \begin{aligned} \sum_{i=0}^{n}\dbinom{n}{i}x^i\cdot\sum_{i=0}^{n}\dbinom{n}{i}x^i&=\sum_{k=0}^{2n}\dbinom{2n}{k}x^k \\ \sum_{i=0}^{n}\sum_{j=0}^{n}\dbinom{n}{i}\dbinom{n}{j}x^{i+j}&=\sum_{k=0}^{2n}\dbinom{2n}{k}x^k \end{aligned} $$ 对照系数可得 $$\sum_{i=0}^k\dbinom{n}{i}\dbinom{n}{k-i}=\dbinom{2n}{k}$$ 令 $k=n$，有 $$\sum_{i=0}^n\dbinom{n}{i}^2=\dbinom{2n}{n}$$ $$\quad$$ ### 例 3 化简 $$\sum_{k=0}^n\dbinom{n}{k}t^k\left(1-t\right)^{n-k}\left[k~\text{mod}~2\right]$$ **解**  因为有 $\left[k~\text{mod}~2\right]=\dfrac{1}{2}\normalsize\left(1+\left(-1\right)^{k+1}\right)$ 所以 $$ \begin{aligned} \sum_{k=0}^n\dbinom{n}{k}t^{k}\left(1-t\right)^{n-k}\left[k~\text{mod}~2\right]&=\frac{1}{2}\sum_{k=0}^n\dbinom{n}{k}t^k\left(1-t\right)^{n-k}\left(1+\left(-1\right)^{k+1}\right) \\ &=\dfrac{1}{2}\left(\sum_{k=0}^n\dbinom{n}{k}t^k\left(1-t\right)^{n-k}-\sum_{k=0}^n\dbinom{n}{k}\left(-t\right)^k\left(1-t\right)^{n-k}\right) \\ &=\dfrac{1-\left(1-2t\right)^n}{2} \end{aligned} $$