# 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.

• $2^{n-i}\binom{n}{i}$ is not the number of ways of choosing at least $i$ elements of a set of $n$ elements. – Thomas Andrews Mar 17 '15 at 23:01
• Shouldn't the right hand side be $\sum_{i=0}^n$, not $\sum_{i=0}^m$? – Thomas Andrews Mar 18 '15 at 3:58
• And do you need $m\leq n$? It doesn't seem like you do. – Thomas Andrews Mar 18 '15 at 4:07

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.

• +1 The right side should actually be $\sum_{i=0}^n$, not $\sum_{i=0}^m$. The problem as stated is wrong. This is essentially the same as my answer, but the men/women phrasing is nice. – Thomas Andrews Mar 18 '15 at 4:00
• @Thomas: It should indeed; thanks for catching that. – Brian M. Scott Mar 18 '15 at 4:08

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

Permit me to observe that there is also a simple algebraic proof. Note the correction in the upper limit of the RHS.

Suppose we are trying to show that $$\sum_{q=0}^m {m\choose q} 2^{n-q} {n\choose q} = \sum_{q=0}^n {n+m-q\choose m} {n\choose q}$$ where $$n\ge m.$$

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

which gives for the LHS $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^n\times (1+z)^n}{z} \sum_{q=0}^m {m\choose q} \frac{1}{(2z)^{q}}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^n\times (1+z)^n}{z} \left(1+\frac{1}{2z}\right)^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^{n-m}\times (1+z)^n}{z^{m+1}} (1+2z)^m \; dz.$$

For the RHS introduce the integral representation $${n+m-q\choose m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m-q}}{z^{m+1}}\; dz$$

which gives for the RHS $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m}}{z^{m+1}}\; \sum_{q=0}^n {n\choose q} \frac{1}{(1+z)^q}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m}}{z^{m+1}}\; \left(1+\frac{1}{1+z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{m+1}} (2+z)^n \; dz.$$

Now put $$z=2w$$ to obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon/2} \frac{(1+2w)^{m}}{(2w)^{m+1}} (2+2w)^n \; 2 \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon/2} 2^{n-m} \frac{(1+2w)^{m}}{w^{m+1}} (1+w)^n \; dw.$$

This matches the integral for the LHS, done.

Remark. It is not difficult to extract coefficients from this integral but that is not necessary because the equality of the two integrals is sufficient (also note that all the sums involved are finite.)

• Nice approach, but any "algebraic proof" which uses complex integrals isn't really an algebraic proof. – Thomas Andrews Mar 18 '15 at 4:04
• This is politely worded, thanks. I hope my contribution finds a place here, if only for variety's sake. This particular application of the Egorychev method is remarkable for the simplicity of the integrals involved. – Marko Riedel Mar 18 '15 at 4:13
• It' a nice approach. I'm also not sure I'd call it simple, but it does look like something that would be useful more generally. – Thomas Andrews Mar 18 '15 at 4:16