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

  • 1
    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.2011-05-13
  • 1
    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$.2011-05-13
  • 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}.$$