Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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

up vote 14 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
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,

share|cite|improve this answer

The book A=B

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.