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

I'm trying to prove that $$\sum_{0\le i\le k} \binom{n}{i}.\binom{m}{k-i} = \binom{m+n}{k}.$$ I got the constants $m!$ and $n!$ out of the sum but I couldn't proceed.

share|cite|improve this question
This is Vandermonde's identity; there are several proofs at the Wikipedia page. – Douglas S. Stones Oct 25 '12 at 21:32
@DouglasS.Stones Just what I was looking for. – user31280 Oct 25 '12 at 21:34
Proof by induction works fine, too. I had to prove this, too. But the algebraic proof on the wikipedia page wasnt my favorite. – Epsilon Oct 25 '12 at 22:16
up vote 5 down vote accepted

To select $k$ peaces of fruit from $m$ apples and $n$ pears, you can also first select a number $0\le i\le k$ of apples you want, select $i$ aplles and $k-i$ pears.

share|cite|improve this answer

Notice that $\binom{m+n}{k}$ is the number of ways of choose $k$ elements between $m+n$ given elements. Then you can think these $m+n$ elements separated in two blocks of $m$ and $n$ elements. So, if you choose
$i$ elements in the block of the $n$ elements and $k-i$ in the block of the $m$ elements, you choose $k$ elements between the $m+n$ given elements.

share|cite|improve this answer

How can you chose $k$ objects from $m+n$?

You chose some ($i$) from the first $m$ and then chose $k-i$ from the second. And $0 \leq i \leq k$...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.