# Vandermonde's Identity: How to find a closed formula for the given summation [duplicate]

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?

-
@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

## marked as duplicate by amWhy, Davide Giraudo, azimut, Old John, nikNov 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.

## 6 Answers

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

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

-
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,

-
add comment