二项式定理及其它

二项式定理及其它

二项式定理

基本定理

二项式定理是用于展开两数相加的幂次的公式:
(1.1)(x+y)n=k=0n(nk)xkynk (x + y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k} \tag{1.1}

我们可以考虑使用组合证明。由于我们可以从nn个括号中任意选取kk个来组成xkx^k的项,这个方案数恰好是(nk){n \choose k},剩下的yy也是同理。因此对应的项的系数就是(nk){n \choose k}(nnk){n \choose n - k}
下面使用归纳法证明:
n=1n = 1的时候:
(x+y)1=x+y=k=01(1k)xky1k (x + y)^1 = x + y = \sum_{k=0}^1 {1 \choose k} x^ky^{1-k}

结论显然成立。
假设对nn成立,求证对n+1n + 1成立:
(x+y)n+1=(x+y)(x+y)n=(x+y)k=0n(nk)xkynk=k=0n(nk)xk+1ynk+k=0n(nk)xkynk+1=xn+1+yn+1+k=0n1(nk)xk+1ynk+k=1n(nk)xkynk+1=xn+1+yn+1+k=1n(nk1)xkynk+1+k=1n(nk)xkynk+1=xn+1+yn+1+k=1n[(nk1)+(nk)]xkynk+1=xn+1+yn+1+k=1n(n+1k)xkynk+1=k=0n+1(n+1k)xkynk+1 \begin{aligned} (x + y)^{n+1} & = (x + y)(x + y)^n \\ & = (x + y)\sum_{k=0}^n {n \choose k} x^ky^{n-k} \\ & = \sum_{k=0}^n {n \choose k} x^{k+1}y^{n-k} + \sum_{k=0}^n {n \choose k} x^ky^{n-k+1} \\ & = x^{n+1} + y^{n+1} + \sum_{k=0}^{n-1} {n \choose k} x^{k+1}y^{n-k} + \sum_{k=1}^n {n \choose k} x^ky^{n-k+1} \\ & = x^{n+1} + y^{n+1} + \sum_{k=1}^{n} {n \choose k - 1} x^{k}y^{n-k+1} + \sum_{k=1}^n {n \choose k} x^ky^{n-k+1} \\ & = x^{n+1} + y^{n+1} + \sum_{k=1}^n \left[{n \choose k - 1}+{n \choose k}\right] x^ky^{n-k+1} \\ & = x^{n+1} + y^{n+1} + \sum_{k=1}^n {n+1 \choose k} x^ky^{n-k+1} \\ & = \sum_{k=0}^{n+1} {n+1 \choose k} x^ky^{n-k+1} \\ \end{aligned}

这样就完成了我们的证明。

简单运用

组合恒等式

y=1y = 1,我们将得到一个很常用的式子:
(1.2)(1+x)n=k=0n(nk)xk (1 + x)^n = \sum_{k=0}^n {n \choose k} x^k \tag{1.2}

x=1x = 1:
(1.3)k=0n(nk)=(1+1)n=2n \sum_{k=0}^n {n \choose k} = (1 + 1)^n = 2^n \tag{1.3}

得到了组合数之和,

x=1x = -1:
(1.4)k=0n(1)k(nk)=0 \sum_{k=0}^n (-1)^k {n \choose k} = 0 \tag{1.4}

得到了组合数的交错和。
通过移项可以得到更进一步的结论::
(1.5)(n0)+(n2)+=(n1)+(n3)+ {n \choose 0} + {n \choose 2} + \dots = {n \choose 1} + {n \choose 3} + \dots \tag{1.5}

结合(1.3)(1.3)可知:
(1.6)(n0)+(n2)+=(n1)+(n3)+=2n1 {n \choose 0} + {n \choose 2} + \dots = {n \choose 1} + {n \choose 3} + \dots = 2^{n-1} \tag{1.6}

导数

现在我们重新考虑这个式子:
(1.2)(1+x)n=k=0n(nk)xk (1 + x)^n = \sum_{k=0}^n {n \choose k} x^k \tag{1.2}

两边同时关于xx求导:
(1.7)n(1+x)n1=k=0n(nk)kxk1 n(1 + x)^{n-1} = \sum_{k=0}^n {n \choose k} \cdot kx^{k-1} \tag{1.7}

x=1x = 1
(1.8)n2n1=k=0nk(nk) n2^{n-1} = \sum_{k=0}^n k{n \choose k} \tag{1.8}

这样我们得到了一个非常有意思的式子。
运用这个式子,我们可以算出:
k=0n(2k+1)(nk)=(n+1)2n \sum_{k=0}^n (2k+1){n \choose k} = (n+1)2^n

事实上,你还可以对(1.8)(1.8)进一步求导,从而得到k2k^2的公式。

组合数的平方和

(1.9)k=0n(nk)2=(2nn) \sum_{k=0}^n {n \choose k}^2 = {2n \choose n} \tag{1.9}

对于这个结论,我们考虑下面的式子:
(1+x)n(1+x)n=(1+x)2n (1 + x)^n(1+x)^n = (1+x)^{2n}

运用二项式定理展开可得:
i=0n(ni)xij=0n(nj)xj=i=0nj=0n(ni)(nj)xixj=k=02n(2nk)xk \begin{aligned} \sum_{i=0}^n {n\choose i} x^i \cdot \sum_{j=0}^n {n\choose j} x^j & = \sum_{i=0}^n\sum_{j=0}^n {n \choose i}{n \choose j} x^ix^j \\ & = \sum_{k=0}^{2n} {2n \choose k} x^k \end{aligned}

考虑等号两边系数同为kk的项,一定满足下面的等式:
(1.10)i=0n(ni)(nki)=(2nk) \sum_{i=0}^n {n \choose i}{n \choose k - i} = {2n \choose k} \tag{1.10}

k=nk = n时:
i=0n(ni)(nni)=i=0n(ni)(ni)=i=0n(ni)2=(2nn) \begin{aligned} \sum_{i=0}^n {n \choose i}{n \choose n - i} & = \sum_{i=0}^n {n \choose i}{n \choose i} \\ & = \sum_{i=0}^n {n \choose i}^2 \\ & = {2n \choose n} \end{aligned}

这样就证明了组合数的平方和的结论。

二项式定理与e\text{e}

根据泰勒展开,我们可以知道:
(1.11)ex=n=0xnn! \text{e}^x = \sum_{n=0}^\infty \frac{x^n}{n!} \tag{1.11}

x=1x = 1就可以得到e\text{e}的无穷展开形式:
(1.12)e=k=01k! \text{e} = \sum_{k=0}^\infty \frac1{k!} \tag{1.12}

而我们平常所熟知的e\text{e}的定义是这样的:
(1.13)e=limn(1+1n)n \text{e} = \lim_{n \rightarrow \infty} \left(1 + \frac1n\right)^n \tag{1.13}

运用二项式定理可以证明泰勒展开的结果与上面的定义等价:
e=limn(1+1n)n=limnk=0n(nk)1nk=limnk=0n1k!i=nk+1nink \begin{aligned} \text{e} & = \lim_{n\rightarrow\infty} \left(1 + \frac1n\right)^n \\ & = \lim_{n\rightarrow\infty} \sum_{k=0}^n {n \choose k} \frac1{n^k} \\ & = \lim_{n\rightarrow\infty} \sum_{k=0}^n \frac1{k!} \frac{\prod_{i=n-k+1}^n i}{n^k} \end{aligned}

由于:
limni=nk+1nink=1 \lim_{n \rightarrow \infty} \frac{\prod_{i=n-k+1}^n i}{n^k} = 1

所以这一项可以去掉。于是就得到了泰勒展开的结果。

多项式定理

与二项式定理,这个定理并不怎么常用。
可能是形式比较复杂,不便于理论分析。
多项式定理是二项式定理的扩展:
(2.1)(x1+x2++xm)n=k1+k2++km=n(nk1  k2    km)x1k1x2k2xmkm (x_1 + x_2 + \dots + x_m)^n = \sum_{k_1 + k_2 + \dots + k_m = n} {n \choose k_1\;k_2\;\dots\;k_m} x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m} \tag{2.1}

其中:
(nk1  k2    km)=n!k1!k2!km! {n \choose k_1\;k_2\;\dots\;k_m} = {n! \over k_1!k_2!\cdots k_m!}

是多项式系数,同时也是多重集合的全排列数量。
组合证明方法与二项式定理类似。同时也可以从二项式定理归纳法而来。

牛顿二项式定理

牛顿二项式定理又称为广义二项式定理:
(3.1)(x+y)α=k=0(αk)xkyαk      (αR,  0  x  <  y) (x + y)^\alpha = \sum_{k=0}^\infty {\alpha \choose k} x^ky^{\alpha - k} \;\;\; (\alpha \in R,\;\color{red}{0 \le \;\mid x\mid\; \lt \;\mid y\mid}) \tag{3.1}

注意红色的字,这是非常重要的限制。
其中:
(αk)=i=αk+1αik! {\alpha \choose k} = {\prod_{i=\alpha - k +1}^\alpha i \over k!}

是在实数域的二项式系数。
不会那么高深的高数知识,不会证......

基本用途

这种形式并不常用,而另外一种形式很常用:
z=x/yz = x/y,那么z  <1\color{red}{\mid z\mid \;\lt 1}
(x+y)α=yα(z+1)α (x + y)^\alpha = y^\alpha(z + 1)^\alpha

所以:
(3.2)(z+1)α=k=0α(αk)xkyαkyα=k=0α(αk)xkykyαkyαk=k=0α(αk)zk=(1+z)α \begin{aligned} (z + 1)^\alpha & = \sum_{k=0}^\alpha {\alpha \choose k} {x^ky^{\alpha-k} \over y^\alpha} \\ & = \sum_{k=0}^\alpha {\alpha \choose k} {x^k \over y^k}\cdot{y^{\alpha-k} \over y^{\alpha-k}} \\ & = \sum_{k=0}^\alpha {\alpha \choose k} z^k \\ & = (1 + z)^\alpha \end{aligned} \tag{3.2}

几何级数

α=n  (nZ)\alpha = -n \; (n \in Z)
(αk)=(nk)=(1)k(n+k1k) {\alpha \choose k} = {-n \choose k} = (-1)^k{n + k - 1 \choose k}

所以:
1(1+z)n=k=0(1)k(n+k1k)zk \frac1{(1+z)^n} = \sum_{k=0}^\infty (-1)^k{n + k - 1 \choose k} z^k

z=zz = -z
1(1z)n=k=0(n+k1k)zk \frac1{(1-z)^n} = \sum_{k=0}^\infty {n+k-1 \choose k}z^k

妙啊!讨厌的1-1不见了!
n=1n=1
11z=k=0zk \frac1{1-z} = \sum_{k=0}^\infty z^k

正是收敛几何级数。
这东西在生成函数里面很常见。
看生成函数之前一定要学好牛顿二项式定理和泰勒展开QAQ。
现在我们来求一下有限几何级数的公式。
注意z  <1\mid z \mid \;\lt 1
(3.3)k=0nzk=k=0zkk=n+1zk=k=0zkzn+1k=0zk=(1zn+1)k=0zk=1zn+11z \begin{aligned} \sum_{k=0}^n z^k & = \sum_{k=0}^\infty z^k - \sum_{k=n+1}^\infty z^k \\ & = \sum_{k=0}^\infty z^k - z^{n+1}\sum_{k=0}^\infty z^k \\ & = (1 - z^{n+1}) \sum_{k=0}^\infty z^k \\ & = {1 - z^{n+1} \over 1-z} \end{aligned} \tag{3.3}

开根运算

之前取α=n\alpha = -n,从而解决了几何级数的问题。
现在取α=1/2\alpha = 1/2,就可以将求平方根变成一个迭代的形式。
并且可以求任意幂次、任意精度的结果。
由于zz有限制,因此需要提项,如:
20=16+4=41+0.25 \sqrt{20} = \sqrt{16+4} = 4\sqrt{1 + 0.25}

这样我们就获得了一个求根号的好方法。


# NULL #