Binomial Theorem

For any positive integer $n$, $(x+y)^n=\sum^n_{k=0} \left(\begin{array}{c} n\\ k \end{array}\right)x^{n-k}y^k.$

#### Proof by Induction:

For $n=1$, $(x+y)^1=x+y=\left(\begin{array}{c} 1\\ 0 \end{array}\right)x^{1-0}y^0+\left(\begin{array}{c} 1\\ 1 \end{array}\right)x^{1-1}y^1=\sum_{k=0}^1 \left(\begin{array}{c} 1\\ k \end{array}\right)x^{1-k}y^k.$

Suppose $\displaystyle (x+y)^{n-1}=\sum^{n-1}_{k=0} \left(\begin{array}{c} n-1\\ k \end{array}\right)x^{(n-1)-k}y^k.$

Consider $(x+y)^n$. \begin{eqnarray*} (x+y)^n&=&(x+y)(x+y)^{n-1}\\ &=&(x+y)\left[\sum^{n-1}_{k=0} \left(\begin{array}{c} n-1\\ k \end{array}\right)x^{(n-1)-k}y^k\right]\\ &=& \sum^{n-1}_{k=0} \left(\begin{array}{c} n-1\\ k \end{array}\right)x^{n-k}y^k + \sum^{n-1}_{j=0} \left(\begin{array}{c} n-1\\ j \end{array}\right)x^{(n-1)-j}y^{j+1}\\ &=&\sum^{n-1}_{k=0} \left(\begin{array}{c} n-1\\ k \end{array}\right)x^{n-k}y^k+\sum^{n-1}_{j=0} \left(\begin{array}{c} n-1\\ (j+1)-1 \end{array}\right)x^{n-(j+1)}y^{j+1}\\ &=&\sum^{n-1}_{k=0} \left(\begin{array}{c} n-1\\ k \end{array}\right)x^{n-k}y^k+\sum^{n}_{k=1} \left(\begin{array}{c} n-1\\ k-1 \end{array}\right)x^{n-k}y^{k}\\ &=&\sum^{n}_{k=0} \left[\left(\begin{array}{c} n-1\\ k \end{array}\right)x^{n-k}y^k\right]-\left(\begin{array}{c} n-1\\ n \end{array}\right)x^0y^n\\ &~&+\sum^{n}_{k=0} \left[\left(\begin{array}{c} n-1\\ k-1 \end{array}\right)x^{n-k}y^{k}\right]-\left(\begin{array}{c} n-1\\ -1 \end{array}\right)x^ny^0\\ &=&\sum^{n}_{k=0} \left[\left(\begin{array}{c} n-1\\ k \end{array}\right)+\left(\begin{array}{c} n-1\\ k-1 \end{array}\right)\right]x^{n-k}y^k\\ &=& \sum^{n}_{k=0} \left(\begin{array}{c} n\\ k \end{array}\right)x^{n-k}y^k \end{eqnarray*} and the theorem is proved!