# Prove that $\binom{m+n}{m}=\sum\limits_{i=0}^m \binom{m}{i}\binom{n}{i}$

I need to proof this following equality :

$$\binom{m+n}{m}=\sum_{i=0}^m \left(\binom{m}{i}\binom{n}{i}\right)$$

This is what I did combinatoric proof:

Left : subset with $m$ members from $m+n$

Right : $\binom{m}{i} \rightarrow$ The number of subsets in set $m$ could also be written as $2^m$ AND $\binom{n}{i} \rightarrow$ the number of subsets with $m$ members from set $n$

In case $n \leq m \implies \binom{n}{i}=2^n$

So this is what I came up with I still can't see why those expression are equal.

Any ideas? Thanks.

They aren’t equal. I’m afraid that your argument makes no sense: $\binom{m}i$ is the number of $i$-element subsets of $[m]$ and is certainly not $2^m$, and $\binom{n}i$ is not the number of $m$-element subsets of $[n]$ unless $i$ happens to equal $m$.

Suppose that you have $m$ men and $n$ women, and you want to choose a committee of $m$ people from this group; clearly $\binom{m+n}m$ is the number of possible committees. Now rewrite the righthand side as

$$\sum_{i=0}^m\binom{m}{m-i}\binom{n}i\;.$$

(Why is this equal to the original righthand side?)

For each $i\in\{0,1,\ldots,m\}$, $\binom{n}i$ is the number of ways to choose $i$ women, and $\binom{m}{m-i}$ is the number of ways to choose $m-i$ men to fill out a committee of $m$ people. Thus, $\binom{m}{m-i}\binom{n}i$ is the number of $m$-person committees that have exactly $i$ women. Summing over the possible values of $i$ gives you the total number of $m$-person committees that can be formed from this collection of $m$ men and $n$ women.

For more information, see the Wikipedia article on Vandermonde’s identity.


Observe that $\binom{m}{i} = \binom{m}{m-i}$. So you select $i$ folks from the $n$ person set and $m-i$ folks from the $m$ person set. These selections are independent, so by rule of product, me multiply. By rule of sum, we add up over all such $i$.

• Looks like someone beat me to it! :-) – ml0105 May 16 '16 at 17:35