Combinatorial proof of $ \sum \limits_{i = 0} ^{m} 2^{n-i} {n \choose i}{m \choose i} = \sum\limits_{i=0}^m {n + m - i \choose m} {n \choose i} $ I've been wondering for a while how to solve (prove) a combinatorial identity, using just combinatorial interpretation:
$$ \sum \limits_{i = 0} ^{m} 2^{n-i} {n \choose i}{m \choose i} = \sum\limits_{i=0}^n {n + m - i \choose m} {n \choose i} $$
($ m \leq n $ ) 
The left hand side is pretty much about choosing any number of elements from the set $ M = \{a_1, \dots, a_m\} $ and then choosing at least the same amount from $ N = \{b_1, \dots, b_n\} $, but I can't see how the right hand side satisfies that.

You have $n$ women in one room and $m$ men in another. You select a total of $m$ people from the combined occupants of the two rooms and send them off to a lecture on combinatorics. Then you pick some subset of the remaining women and send them off to a lecture on topology, and send everyone else home. Let $i$ be the number of women sent to the lecture on combinatorics; then there are $\binom{n}i\binom{m}{m-i}2^{n-i}=\binom{n}i\binom{m}i2^{n-i}$ ways to make the selection, so the total number of possibilities is 
$$\sum_{i=0}^m\binom{n}i\binom{m}i2^{n-i}\;.$$
Alternatively, you could select $i$ women to be sent home, and then from the remaining occupants of the two rooms select $m$ to attend the combinatorics lecture; the remaining $n-i$ women will attend the topology lecture. Clearly this can be done in 
$$\sum_{i=0}^n\binom{n}i\binom{n+m-i}m$$
ways. (Note that $i$ can be as much as $n$ in this approach, so the sum should have $n$ as upper limit.) Each procedure sends $m$ people to the combinatorics lecture and some subset of the remaining women to the topology lecture, and each allows for every possible assignment of that kind, so they count the same thing.
