# Finding a combinatorial argument for an interesting identity: $\sum_k \binom nk \binom{m+k}n = \sum_i \binom ni \binom mi 2^i$

Consider the following identity

$${{n}\choose{0} }{m\choose n} + {n\choose 1}{{m+1} \choose n}+ \cdots +{n\choose n}{{m+n} \choose n} =\sum_{i=0}^{\min (m ,n)} {n\choose i}{m\choose i}2^i$$

The right hand side looks really neat to me but I can't find any combinatorial argument to this.I'm totally stuck on how to approach. I'd like hints and not full solutions.

EDIT I guess asking for a hint was a bit too much for this question. Apologies.

• For the sake of future reference, I would like to mention that both sides are indeed equal to $$[x^m y^n] \frac{1}{1-x-y-xy},$$ where the bracket notation extracts the coefficient of $x^m y^n$ from the Taylor series. Apr 7, 2015 at 6:13

You have $n$ women in Room A and $m$ men in Room B. For some $k\in\{0,\ldots,n\}$ you pick $k$ of the women and move them into Room B; this can be done in $\binom{n}k$ ways. Then you pick $n$ of the people in Room B and move them to Room C; this can be done in $\binom{m+k}n$ ways, so there are altogether
$$\sum_k\binom{n}k\binom{m+k}n$$
ways to carry out this process. The result of the process is $n$ people in Room C, $n-k$ women in Room A for some $k$, and $m+k-n$ people in Room B. If there are $\ell$ men in Room C, then there are $m-\ell$ men in Room B.
We might instead begin by simply picking $\ell$ men from Room B and $n-\ell$ women from Room A and moving them to Room C; this leaves $\ell$ women in Room A, and we conclude by moving any subset of them into Room B$. This process can be carried out in $$\sum_\ell\binom{n}{n-\ell}\binom{m}\ell2^\ell=\sum_\ell\binom{n}\ell\binom{m}\ell2^\ell$$ ways. Clearly the two procedures have the same set of possible outcomes:$n$of the people in Room C, all of the other men still in Room B, and possibly some of the other women in Room B instead of Room A. Thus, $$\sum_k\binom{n}k\binom{m+k}n=\sum_k\binom{n}k\binom{m}k2^k\;.$$ Permit me to contribute a proof complex variables, for variety's sake, which is an instructive exercise. Suppose we seek to verify that $$\sum_{q=0}^n {n\choose q} {m+q\choose n} = \sum_{q=0}^{\min(m,n)} {n\choose q}{m\choose q}2^q.$$ with$n,m$a positive integers. For the LHS introduce the integral representation $${m+q\choose n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+q}}{z^{n+1}} \; dz$$ which gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \sum_{q=0}^n {n\choose q} (1+z)^q\; dz$$ or alternatively $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} (2+z)^n \; dz.$$ For the RHS start by observing that it is symmetric in$m$and$n$so we may assume that$m\ge n.$Now introduce the integral representation $${m\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{q+1}} \; dz$$ which gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \sum_{q=0}^n {n\choose q} 2^q \frac{1}{z^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \left(1+\frac{2}{z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \frac{(z+2)^n}{z^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} (2+z)^n \; dz.$$ We have equality of the LHS and the RHS which was to be shown. Addendum. If we had not observed the symmetry here we would get for$n\ge m$the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{m+1}} (2+z)^m \; dz.$$ Put$z=2/w\$ in this integral to get $$-\frac{1}{2\pi i} \int_{|w|=R} \frac{(1+2/w)^{n}}{(2/w)^{m+1}} (2+2/w)^m \times\left(-\frac{2}{w^2}\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(w+2)^n}{w^n} \frac{w^{m+1}}{2^{m+1}} \frac{(2w+2)^m}{w^m} \times\left(\frac{2}{w^2}\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(w+2)^n}{w^{n+1}} (w+1)^m \; dw$$