Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
You state: 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 evenly must be even. Here by 'pairs not split evenly' are you referring to the number of pairs for which both are outside or inside? –  114 Apr 21 '13 at 23:46
    
Yes. I eliminated the word "evenly." I hope it is clearer. –  Adam Saltz Apr 22 '13 at 0:31
    
Thanks, sometimes I get too caught up on wording. –  114 Apr 22 '13 at 0:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.