Combinatorial Proof of a Binomial Coefficient Identity

Question

I am looking to prove the following identity combinatorially:

$\sum_k$ $n \choose 2k$ $2k \choose k$ $2^{n-2k}$ = $2n \choose n$

Clearly the RHS counts the number of ways to choose n elements out of a set containing an even number of elements. Specifically, we choose half the set. The LHS counts the same by instead choosing all possible even subsets of n (those with even cardinality) and then choosing whether the remaining terms are in or out of this subset. However, I am not sure how the second term fits in then.

Answer 1

Note that $2n$ doesn't appear on the left side.

Here is one way to think about the left. We want to choose a set $S$ of $n$ elements from $2n$. Label the $2n$ elements $a_1, b_1, \ldots, a_n, b_n$. For each pair $\{a_i,b_i\}$, it's possible that both elements lie in $S$, or that neither element lies in $S$, or that one element lies in $S$ and the other doesn't. For every pair which lies entirely inside $S$ there must be another pair which lies entirely outside of $S$. Thus the number of pairs not split must be even.

Fix $k$. Set aside $n - 2k$ pairs to be split. For the remaining $2k$ pairs, choose $k$ to be entirely inside $S$. The remaining $k$ necessarily lie entirely outside of $S$. Now from those $n - 2k$ pairs set aside, we must choose whether $a_i$ or $b_i$ lies in $S$. Evidently the number of possibilities is $$\binom{n}{n - 2k}\binom{2k}{k}2^{n-2k} = \binom{n}{2k}\binom{2k}{k}2^{n-2k}.$$

Now sum up over $k$ (and convince yourself that you have enumerated all the possibilities).