# binomial expansion

$\displaystyle \binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}$

$\displaystyle \left(1+x\right)^{n} = \left(1+x\right)\left(1+x\right)^{n-1}$

how do I use binomial expansion on the second equations for the right hand side and convert it to the first equation. The left hand side is obvious, but I m not sure how to do the right hand side. Please give me some hints

thanks

-
The LHS is the coefficient of $x^k$ in $(1+x)^n$, right? So, you could try to compute the coefficients of $x^k$ in $(1+x)^{n-1}$ and in $x(1+x)^{n-1}$ respectively, and see why this gives you the answer. –  Did May 13 '11 at 15:16
Do you mean you want to derive the first equation using the second? Expand $(1+x)^{n-1}$ as a series; multiply with $1+x$, and compare coefficients with the expansion of $(1+x)^n$. –  Guess who it is. May 13 '11 at 15:16
thanks you two, I will give it a try now –  justinliu May 13 '11 at 15:22

Binomial expansion of both sides of $$\left(1+x\right)^{n} = \left(1+x\right)\left(1+x\right)^{n-1}$$ gives $$\sum_{k=0}^n \binom{n}{k} x^k = \left(1+x\right)\sum_{k=0}^{n-1} \binom{n-1}{k} x^k$$ by distributivity on the right hand side we find $$\left(\sum_{k=0}^{n-1} \binom{n-1}{k} x^k \right)+\left(\sum_{k=0}^{n-1} \binom{n-1}{k} x^{k+1} \right) = \left(\sum_{k=0}^{n} \binom{n-1}{k} x^k \right)+\left(\sum_{k=0}^{n} \binom{n-1}{k-1} x^{k}\right)$$ the limits of the summations do not change the sum because $\binom{n-1}{n} = 0$, $\binom{-1}{n} = 0$. Thus we have $$\sum_{k=0}^n \binom{n}{k} x^k = \sum_{k=0}^{n} \left(\binom{n-1}{k} + \binom{n-1}{k-1}\right) x^k$$ and extracting the $x^k$ coefficients from both sides gives the identity $$\displaystyle \binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}.$$