Proving through combinatorial argument $\sum_{i=0}^k \binom{m+k-i-1}{k-i}\binom{n+i-1}{i} = \binom{m+n+k-1}{k}$

Question

I am attempting to solve this counting problem through combinatorial argument. The following is the equation I am given:

$$\sum_{i=0}^k \binom{m+k-i-1}{k-i}\binom{n+i-1}{i} = \binom{m+n+k-1}{k}$$

To be honest I'm pretty lost with this one... This reminds me of problems where you use pirates and gold, but I am not sure what is being counted in either of side of this equation. I keep trying to think of how we are partitioning a given set, but I can't come up with an example.

Thanks!

Answer 1

HINT: Let $A=\{0,1,2,\ldots,m+n+k-2\}$; we want to count the subsets of $A$ of cardinality $m+n-1$.

On the one hand this is clearly

$$\binom{m+n+k-1}{m+n-1}=\binom{m+n+k-1}k\;,$$

since $|A|=m+n+k-1$.

On the other hand, if $S$ is such a subset, there is a unique $\ell_S\in S$ such that $n-1$ elements of $S$ are less than $\ell_S$, and $m-1$ elements of $S$ are greater than $\ell_S$. Clearly the smallest possible value of $\ell_S$ is $n-1$, and with a little work you can calculate that the largest possible value of $\ell_S$ is $n+k-1$. If we let $i_S=\ell_S-n+1$, the range of possible values of $i_S$ is from $0$ through $k$. For each of the possible values of $i_S$ we want to count the sets $S$ having that value; then we want to sum over the possible values of $i_S$.

• Given $i$, how many ways are there to choose $m-1$ elements of $A$ that are less than $\ell=n+i-1$?
• And how many ways are there to choose $n-1$ elements of $A$ that are greater than $\ell=n+i-1$?
• Putting the pieces together, how many subsets $S$ of $A$ with cardinality $m+n-1$ have $i_S=i$?

Now sum over the possible values of $i$ and show that your summation is equivalent to

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