3
$\begingroup$

$\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

  • 0
    thanks you two, I will give it a try now2011-05-13

1 Answers 1

3

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}.$