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

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?

-

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

@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

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

-

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

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,

-
-