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.
 A: 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\;.$$
A: 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 $$
which is the form we sought.
