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?
$\begingroup$
$\endgroup$
0
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
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}$.
$\begingroup$
$\endgroup$
0
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}$$
answered Jun 26, 2011 at 23:42
$\begingroup$
$\endgroup$
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,
answered Jun 26, 2011 at 23:39
$\begingroup$
$\endgroup$
