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.

This question already has an answer here:

I've stumbled upon the following challenging question. Find a closed formula for the following summation $$ S(a,b,n) = \sum_{k=0}^n {a \choose k} {b \choose n-k}$$ for all possible parameters $a,b$.

Anyone happens to see how to solve this one?

share|improve this question

marked as duplicate by amWhy, Davide Giraudo, azimut, Old John, Najib Idrissi Nov 16 '13 at 16:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

9  
    
@amWhy, Davide Giraudo, azimut, Old John, nik "This question has been asked before and already has an answer". Sorry but this is not true, at least regarding the question indicated, since this other question is more recent by 20 months. Any reason why you decided to close this one instead? –  Did Nov 16 '13 at 17:40
    
@DavideGiraudo See comment above. –  Did Nov 22 '13 at 9:59
    
@azimut See comment above. –  Did Nov 22 '13 at 9:59
    
@OldJohn See comment above. –  Did Nov 22 '13 at 10:00
show 1 more comment

5 Answers 5

up vote 13 down vote accepted

Since ${a\choose k}$ is the coefficient of $x^k$ in the polynomial $(1+x)^a$ and ${b\choose n-k}$ is the coefficient of $x^{n-k}$ in the polynomial $(1+x)^b$, the sum $S(a,b,n)$ of their products collects all the contributions to the coefficient of $x^n$ in the polynomial $(1+x)^a(1+x)^b=(1+x)^{a+b}$.

This proves that $S(a,b,n)={a+b\choose n}$.

share|improve this answer
add comment

A counting argument:

If there are $a$ items of type A and $b$ items of type B, then

$$\sum_{k=0}^{n} {a \choose k} {b \choose n-k}$$

is the number of ways to choosing $n$ items from them: choose $k$ of type A and $n-k$ of type B, vary $k$ from $0$ to $n$ and add up.

Thus the sum you seek is $${a+b \choose n}$$

share|improve this answer
1  
This is the best answer so far. Anyone who doesn't understand it will learn something valuable by coming to understand it. –  Michael Hardy Jun 27 '11 at 0:56
    
+1,this is indeed the best answer! –  Quixotic Sep 5 '11 at 19:45
add comment

One way to solve this is by using generating series. With generating series, we barely have to think about what we are doing, and arrive at the answer nicely. Consider $$\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{a}{k}\binom{b}{n-k}x^{n}.$$

Switching the order of summation, this becomes

$$\sum_{k=0}^{\infty}\binom{a}{k}\sum_{n=k}^{\infty}\binom{b}{n-k}x^{n}=\sum_{k=0}^{\infty}\binom{a}{k}x^{k}\sum_{n=0}^{\infty}\binom{b}{n}x^{n}.$$ Then, by the binomial theorem this is $$\left(1+x\right)^{a}\left(1+x\right)^{b}=(1+x)^{a+b}.$$

Since the $n^{th}$ coefficient of this is $\binom{a+b}{n}$, we see that $$\sum_{k=0}^n\binom{a}{k}\binom{b}{n-k}=\binom{a+b}{n}.$$

Hope that helps,

share|improve this answer
add comment

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