# Combinatorial Proof of a Binomial Coefficient Identity

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.

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).
{"ft_lang_label":"__label__en","ft_lang_prob":0.9003724,"math_prob":0.9994896,"size":519,"snap":"2020-24-2020-29","text_gpt3_token_len":129,"char_repetition_ratio":0.1223301,"word_repetition_ratio":0.0,"special_character_ratio":0.24277456,"punctuation_ratio":0.06930693,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9994629,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-12T13:44:59Z\",\"WARC-Record-ID\":\"<urn:uuid:251ae0d7-cf38-40cf-ae65-632675f50fe0>\",\"Content-Length\":\"144563\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:83b5a5a3-dd94-4252-be14-d46b39bf97ef>\",\"WARC-Concurrent-To\":\"<urn:uuid:6b9e5379-61da-4edc-ad16-ae97f426f830>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/368676/combinatorial-proof-of-a-binomial-coefficient-identity\",\"WARC-Payload-Digest\":\"sha1:IQ6UEOHAHM5T4W34LBBNAVRQGNHAJKSD\",\"WARC-Block-Digest\":\"sha1:GLMZFIUTKVJY5JPBQYKEGJR72DJ25XPA\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593657138718.61_warc_CC-MAIN-20200712113546-20200712143546-00350.warc.gz\"}"}