How to find a combinatorial proof for the following sum?

Question

I'm trying to find a combinatorial proof for the following sum:

$$\sum_{k=0}^{n} 2^{2n-2k} \binom{2n}{2k} \binom{2k}{k} = \binom{4n}{2n}$$

I tried to ask and answer this question from both sides: How many binary numbers of length 4n have exactly 2n zeros?

However, I'm having trouble answering this question for the left side. I would appreciate any suggestion!

Answer 1

There are $4n$ people total, consisting of $2n$ married couples. How many ways are there to choose a subset of exactly half of the people? Obviously, one answer to this question is $\binom{4n}{2n}$.

More specifically, for each $k\in \{0,1,\dots,n\}$, we can ask the number of ways to select $2n$ people such that exactly $2k$ couples are together, meaning they are either both chosen or both not chosen. The number of ways is exactly $2^{2n-2k}\binom{2n}{2k}\binom{2k}k$, so summing over $k$ leads to the left-hand-side.

Here is a more detailed proof, behind a spoiler block in case you want to try to find it yourself.

The number of separated couples must be even, because $$2n=\text{#(separated couples)}+2\times\text{#(couples where both chosen)}$$ Since $\text{# (separated couples)}+\text{# (together couples)}=2n$, this further implies there must be an even number of together couples, justifying why are counting the number of ways to choose $2k$ together couples.

If there are $2k$ together couples, you can choose which couples are together in $\binom{2n}{2k}$ ways.

Each separated couple has one chosen spouse and one non-chosen spouse. Therefore, the couples which are together must have an equal number of chosen and non-chosen people. This implies that exactly half of the together couples are chosen. Therefore, there are $\binom{2k}k$ ways to choose which together couples are chosen.

Finally, for each of the $2n-2k$ remaining separated couples, there are $2^{2n-2k}$ ways to select one spouse from each couple.

Answer 2

Let $X$ be a set of size $2n.$ Then $\binom{4n}{2n}$ can be seen to count the number of ordered pairs of (not necessarily disjoint) subsets of $X,$ $(A,B)$ with $|A|+|B|=2n.$ (This can be seen as counting subsets of $X\times\{1,2\}$ of size $2n,$ with $A$ corresponding to the elements of $X\times\{1\}$ and $B$ corresponding to $X\times\{2\}.$)"

On the other hand, $2^{2n-2k}\binom{2n}{2k}\binom{2k}{k}$ counts the number of ordered tuples $(A',B',C')$ of disjoint subsets with $|A'|=|B'|=k.$. So the sum counts tuples $(A',B',C')$ of disjoint subsets with $|A'|=|B'|.$

Now, $|B|=2n-|X\setminus B|,$ so if $(A,B)$ is in the first set, then $|A|=|B^c|,$ where $B^c=X\setminus B$ is the complement of $B.$

From $(A,B)$ we construct sets $(A',B',C')=(A\setminus B^c,B^c\setminus A, A\cap B^c).$ Show $|A'|=|B'|,$ and $A',B',C'$ are disjoint.

In reverse, given disjoint $(A',B',C'),$ with $|A'|=|B'|,$ we can find $A=A'\cup C',$ and $B=(B'\cup C')^c.$ Show $|A|+|B|=2n.$

Show these operations are inverses.

---

Example, when $n=2.$ We take $X=\{1,2,3,4\}$ and $S=\{(1,1),(2,1),(4,1),(2,2)\}$ and map it to $A=\{1,2,4\}$ and $B=\{2\}.$

Then $B^c=\{1,3,4\}$ and so $A'=\{2\},B'=\{3\},$ and $C'=\{1,4\}.$

Answer 3

$2n$ people were voting to go either to the beach or to the mountain. Each people was given two balls: one marked as first preference and the other marked as second preference, then they voted by dropping the balls into beach box and/or mountain box. Both boxes contained equal number of balls after the vote ended. How many possibilities are there?

Right Hand Side

$2n $ out of $4n$ balls went into the mountain box, the rest went into the beach box. Number of possibilities:

$$ \binom{4n}{2n} $$

Left Hand Side

$2k$ out of $2n$ people put both of their balls into a box: $k$ people put both of their votes into mountain box, $k$ other people put both of their votes into beach box, the remaining $2n-2k$ people split their votes between the two boxes. Number of possibilities:

$$ 2^{2n-2k}\binom{2n}{2k}\binom{2k}{k} $$

If we sum for all possible $k$, we then end up with the total number of possibilities that the two boxes ended up containing equal number of balls.

Conclusion

Since both LHS and RHS count the same object, they must be equal:

$$ \sum_{k=0}^{n}2^{2n-2k}\binom{2n}{2k}\binom{2k}{k} = \binom{4n}{2n} $$