10
$\begingroup$

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?

  • 9
    http://en.wikipedia.org/wiki/Vandermonde's_identity2011-06-26

5 Answers 5

14

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

14

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

  • 1
    This is the best answer so far. Anyone who doesn't understand it will learn something valuable by coming to understand it.2011-06-27
5

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,

3

http://en.wikipedia.org/wiki/Vandermonde%27s_identity

2

The book A=B
http://www.math.upenn.edu/~wilf/AeqB.html