Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  Did May 13 '11 at 15:16
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$. –  J. M. May 13 '11 at 15:16
    
thanks you two, I will give it a try now –  justinliu May 13 '11 at 15:22

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.