Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

Question

A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.

Answer 1

The captain of the pirate starship Free Enterprise finds $m$ Martians and $n$ Neptunians in a bar. In how many ways can she select a crew of $j$ creatures for a raid on Jupiter?

The right-hand side $\binom{m+n}{j}$ counts the number of ways to select $j$ creatures from the $m+n$ creatures available.

So does the left-hand side. For she could select $0$ Martians and $j$ Neptunians. This can be done in $\binom{m}{0}\binom{n}{j}$ ways.

Or else she could select $1$ Martian and $j-1$ Neptunians. This can be done in $\binom{m}{1}\binom{n}{j-1}$ ways.

Or else she could select $2$ Martians and $j-2$ Neptunians. This can be done in $\binom{m}{2}\binom{n}{j-2}$ ways.

And so on. Thus the number of ways to recruit $j$ creatures is given by the sum on the left-hand side.

Comment: The result, and the reasoning, remain correct even if, for example, $j>n$. All we need to do is to define $\binom{u}{v}$ to be $0$ if $u<v$.