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} $

Solution 1:

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.

Solution 2:

Let $A,B$ be disjoint with $|A|=n$ and $|B|=m$.

On the left hand side, replace $\binom{m}{i}=\binom{m}{m-i}$.

Let $$T=\left\{(C_1,C_2)\mid C_1\subseteq A\cup B, C_2\subseteq A, |C_1|=m, C_1\cap C_2=\emptyset\right\}$$

Define $f,g:T\to \mathbb N$ by: $$\begin{align} f&:(C_1,C_2)\mapsto |C_1\cap A|\\ g&:(C_1,C_2)\mapsto |C_2| \end{align}$$

The $$|T|=\sum_{i=0}^{\infty} \left|f^{-1}(i)\right| = \sum_{i=0}^{\infty} \left|g^{-1}(i)\right|$$

Now, $f^{-1}(i)$ can be counted by picking $i$ elements of $A$ and $m-i$ elements of $B$ to get $C_1$, and then any subset of the remaining $n-i$ elements of $A$ to get $C_2$. So $$\left|f^{-1}(i)\right| = 2^{n-i}\binom{n}{i}\binom{m}{m-i}$$

And $g^{-1}(i)$ can be counted by picking $i$ elements of $A$ for $C_2$, and then any $m$ elements of the remaining $m+n-i$ elements of $A\cup B$ to get $C_1$. So $$\left|g^{-1}(i)\right|= \binom{n}{i}\binom{n+m-i}{m}$$

Finally, the counts for $f^{-1}$ are zero if $i>m$ and the count for $g^{-1}$ are ero for $i>n$, supporting my comment above that the question needs to be corrected to have $\sum_{i=0}^n$ on the right, not $\sum_{i=0}^m$.