Vandermonde's Identity: How to find a closed formula for the given summation 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?
 A: 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,
A: http://en.wikipedia.org/wiki/Vandermonde%27s_identity
A: The book A=B
http://www.math.upenn.edu/~wilf/AeqB.html 
A: 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: 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}$$
