# Multiplication Principle and Inclusion-Exclusion: $2^n = \sum_{i = 0}^n (-1)^i \binom{n}{i} \binom{2n - 2i}{n - 2i}$

I began to compose an unnecessarily complicated answer to this question:

If we had 25 people all who have 2 different balls, how would you work out how many combinations there would be if we want to choose 25 balls, but no person can have both of their balls in the choice?

The most direct way is to visit each of the twenty-five people and choose one ball for a total of $2^{25}$ choices. My convoluted solution makes use of inclusion-exclusion as follows:

Let $A_i$ be the set of all 25-ball combinations that contain both of person $i$'s balls. Since we want the number of ways in which no person has both of their balls chosen, we want to compute $$\binom{50}{25} - \left| \bigcup_{i=1}^{25} A_i \right|.$$ By the principle of inclusion and exclusion, this becomes \begin{align*} \binom{50}{25} - \left| \bigcup_{i=1}^{25} A_i \right| &= \binom{50}{25} - \sum_{i = 1}^{25} (-1)^{i+1} \binom{25}{i} |A_1 \cap \cdots \cap A_i|\\ &= \binom{50}{25} - \sum_{i = 1}^{25} (-1)^{i+1} \binom{25}{i} \binom{50 - 2i}{25 - 2i}\\ &= \sum_{i = 0}^{25} (-1)^i \binom{25}{i} \binom{50 - 2i}{25 - 2i}\\ \end{align*}

I find that I am unable to directly simplify this to $2^{25}$ without appealing to the combinatorial argument I made at the beginning. Note that the terms in the summation are all zero for $i \geq 13$.

One could generalize the problem slightly to allow for $n$ people each with two balls, in which case we would obtain $$2^n = \sum_{i = 0}^n (-1)^i \binom{n}{i} \binom{2n - 2i}{n - 2i}.$$ Is there a non-combinatorial proof of this fact that I'm overlooking?

Since $$\binom{2n-2i}{n-2i}=\binom{2n-2i}{n}$$ so

$$\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{2n-2i}{n}=[x^n]\sum_{i=0}^{n}(-1)^i\binom{n}{i}(1+x)^{2n-2i}=[x^n](1+x)^{2n}[1-(1+x)^{-2}]^n\cdot=[x^n]((1+x)^2-1)^n=[x^n]x^n(x+2)^n=2^n$$

• @AustinMohr,No,you are wrong,because $n-2i=25-2\cdot 1=23$, In fact,we use well known indentity $$\binom{n}{i}=\binom{n}{n-i}$$ – math110 May 29 '15 at 0:35
• I can't use $\binom{2n-2i}{n-2i}=\binom{2n-2i}{2i}$, because I only use $\binom{2n-2i}{n-2i}=\binom{2n-2i}{n}$,you can let $n=25,i=1$, then we have $\binom{48}{23}=\binom{48}{25}$!! – math110 May 30 '15 at 1:56
• I don't know why I've been so dense with this identity. I see you are correct now. Thank you. – Austin Mohr May 30 '15 at 5:14

Here is a solution using complex variables sometimes known as the Egorychev method.

Suppose we seek to evaluate $$S(n) = \sum_{q=0}^n {n\choose q} (-1)^q {2n-2q\choose n-2q}.$$

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

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

This last integral evaluates by inspection to $$[z^n] (1+2z)^n = {n\choose n} 2^n = 2^n,$$ as claimed.

This MSE link points to a similar computation.

• Thanks for the enlightening answers. Perhaps I'll finally learn to turn to complex methods for binomial sums. – Austin Mohr May 28 '15 at 16:50