The Binomial Theorem 二項式定理

The Binomial Theorem

$\displaystyle(x+y)^n=\sum^{n}_{k=0} {n\choose k} x^k y^{n-k}$         (4.2)

Proof of the Binomial Theorem by Induction:
When n=1, Equation (4.2) reduces to

$\displaystyle x+y={1\choose 0}x^0y^1+{1\choose 1}x^1y^0=y+x$

Assume Equation (4.2) for n-1. Now,

$\displaystyle\begin{array}{rcl} (x+y)^n&=&(x+y)(x+y)^{n-1} \\ \\ &=&\displayst... ...} x^{k+1}y^{n-1-k} + \sum^{n-1}_{k=0} {n-1\choose k} x^ky^{n-k} \\ \end{array}$

Letting i=k+1 in the first sum and i=k in the second sum, we find that

$\begin{array}{rcl} (x+y)^n&=&\displaystyle\sum_{n}{i=1} {n-1\choose i-1}x^iy^{n... ...y^n \\ \\ &=&\displaystyle\sum^{n}_{i=0}{n\choose i}x^iy^{n-i} \\ \end{array}$

where the next to last equality follows by Equation (4.1). By induction the theorem is now proved.          $\rule[0.02em]{1.0mm}{1.5mm}$

Combinatorial Proof of the Binomial Theorem:
Consider the product $(x_1+y_1)(x_2+y_2)\cdots(x_n+y_n)$. Its expansion consists of the sum of 2n terms, each term being the product of n factors. Further, each of the 2n terms in the sum will contain as a factor either xi or yi for each i=1,2,...,n. For example, (x1+y1)(x1+y1)=x1x2+x1y2+y1x2+y1y2 Now, how many of the 2nterms in the sum will have as factors k of the xi's and (n-k) of the yi's? As each term consisting of k of the xi's and (n-k) of the yi's corresponds to a choice of a group of k from the n values x1,x2,...,xn, there are $\displaystyle{n\choose k}$ such terms. Thus, letting xi=x, yi=y, i=1,...,n, we see that

$\displaystyle(x+y)^n=\sum^{n}_{k=0} {n\choose k} x^k y^{n-k}$         $\rule[0.02em]{1.0mm}{1.5mm}$