# Prove the identity $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{l}=\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r+l-n}2^r$ for $m,n\in\mathbb{N}$

I would like to find out how to prove the following identity, assuming it is correct:

$\displaystyle\sum_{r=0}^n\binom{n}{r}\binom{m+r}{l}=\sum_{r=0}^n\binom{n}{r}\binom{m}{r+l-n}2^r$ for $m,n\in\mathbb{N}$ and $0\le l\le m+n$.

This is a generalization of a problem that was recently posed, https://math.stackexchange.com/questions/962256, and is also related to an earlier problem, Alternative combinatorial proof for $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$

Here’s a combinatorial proof.

You have $n$ women in one room and $m$ men in another. You pick $r$ of the women, move them into the room with the men, and then pick $\ell$ of the people in that room and move them to a third room. There are

$$\binom{n}r\binom{m+r}\ell$$

possible outcomes, so

$$\sum_{r=0}^n\binom{n}r\binom{m+r}\ell\;,$$

is the total number of possible outcomes when $r$ is allowed to be anything. The outcomes are simply the distributions that have $\ell$ of the $n+m$ people in the third room, all of the remaining men in the second room, and the remaining women distributed arbitrarily between the first two rooms.

Now let’s look at the other side. If $k=n-r$, we have

\begin{align*} \sum_{r=0}^n\binom{n}r\binom{m}{r+\ell-n}2^r&=\sum_{k=0}^n\binom{n}k\binom{m}{\ell-k}2^{n-k} \end{align*}\;.

For a fixed $k$ there are $\dbinom{m}{\ell-k}$ ways to pick $\ell-k$ men to be moved to the third room, and there are $\dbinom{n}k$ ways to pick $k$ women to fill out the required complement of $\ell$ people in the third room. There are then $2^{n-k}$ ways to choose some — possibly none — of the women remaining in the first room for transfer to the second room.

Both sides of the proposed identity therefore count the number of ways of transferring $\ell$ of the $n+m$ people to the third room and in addition possibly transferring some of the women remaining in the first room to the second.

• Thanks for this solution! (I was trying to come up with something like this for the first problem to which I linked, but I wasn't able to.) – user84413 Oct 12 '14 at 20:58
• @user84413: You’re welcome! Cute problem; it was fun. – Brian M. Scott Oct 12 '14 at 20:59
• @BrianM.Scott Welcome back. (+1) – Marko Riedel Oct 12 '14 at 22:05
• @Marko: Thanks! – Brian M. Scott Oct 12 '14 at 22:07

By way of enrichment here is a solution using basic complex variables.

Introduce the integral representation $${m+r\choose l} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+r}}{z^{l+1}} \; dz.$$

This gives the following integral for the sum on the LHS: $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{l+1}} \sum_{r=0}^n {n\choose r} (1+z)^r \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{l+1}} (2+z)^n \; dz.$$

Introduce another integral representation $${m\choose r+l-n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{r+l-n+1}} \; dz.$$

This gives the following integral for the sum on the RHS: $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{l-n+1}} \sum_{r=0}^n {n\choose r} \left(\frac{2}{z}\right)^r \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{l-n+1}} \left(1+\frac{2}{z}\right)^n \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{l-n+1}} \left(\frac{z+2}{z}\right)^n \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^m}{z^{l+1}} (z+2)^n \; dz.$$

The integrals on the LHS and the RHS are the same, QED.

Apparently this method is due to Egorychev. A trace as to when it appeared on MSE and by whom starts at this MSE link.

• Thanks for this nice solution. (This gives me a good excuse to review basic complex variables.) – user84413 Oct 12 '14 at 20:48