4
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – 114
    Apr 21, 2013 at 23:46
  • $\begingroup$ Yes. I eliminated the word "evenly." I hope it is clearer. $\endgroup$
    – Adam Saltz
    Apr 22, 2013 at 0:31
  • $\begingroup$ Thanks, sometimes I get too caught up on wording. $\endgroup$
    – 114
    Apr 22, 2013 at 0:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .