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.

Is there a closed form expression for $\displaystyle\sum_{k=0}^n \binom{2n}{2k}$?

A student I tutor was asking me about this and I didn't know. I know if this had a $k$ instead of $2k$, this sum would just be $(2n)^n$ but summing over evens complicates things. Is there even an asymptotic form for this?

share|improve this question
1  
Sure, it is half the sum of all. –  André Nicolas May 8 at 20:20
    
It's $2^{2n-1}$. –  Lucian May 8 at 20:23
    
@Lucian Why the LHS is $\large 1$ and the RHS is $\large 1/2$ when $\large n = 0$ ?. –  Felix Marin Jul 13 at 2:12
    
@FelixMarin: $n\le0$ are degenerate cases. Otherwise, it even works for non-integers, as long as they're strictly positive. –  Lucian Jul 13 at 2:23
    
@Lucian That's because we usually start counting from ONE. Thanks. –  Felix Marin Jul 13 at 3:20

4 Answers 4

Hint: Use the binomial theorem to compute $$ 0^{2n}=(1-1)^{2n} $$ and $$ 2^{2n}=(1+1)^{2n} $$

share|improve this answer
    
Oh, I just did this using generating functions and got that as well. I just wonder if there's a good counting argument for why this identity holds. –  Clark Kent May 8 at 20:22
    
@ClarkKent: it's one of those things that once you see it, you'll never forget it :-) –  robjohn May 8 at 20:28

The set of evensized subsets of $\{1,\ldots,2n\}$ is in bijection with the power set of $\{1,\ldots,2n-1\}$: In one direction just drop $2n$ if necessary, in the other direction do or don't add $2n$ to ensure correct parity. This bijection shows that $$\sum_{k=0}^n{2n\choose 2k}=2^{2n-1}. $$

share|improve this answer

Since $\binom{2n}{k}$ is the number of subsets of $\{1,\ldots,2n\}$ with exactly $k$-elements, $$\sum_{k=0}^{n} \binom{2n}{2k} = \binom{2n}{0} + \binom{2n}{2} + \binom{2n}{4} + \ldots + \binom{2n}{2n}$$ is the number of subsets of $\{1,2,\ldots,2n\}$ which have an even number of elements.

For any nonempty, finite set $X$, exactly half the subsets of $X$ have even cardinality, and the other half have odd cardinality. To see this, fix some element $p \in X$. Define a function $f : \mathscr{P}(X) \to \mathscr{P}(X)$ by

$$ f(A) = \begin{cases} A \cup \{p\} & \text{ if } p \notin A \\ A \setminus \{p\} & \text{ if } p \in A \\ \end{cases} $$

The effect of $f$ is to toggle whether or not $p$ belongs to a subset. Note $f$ is a bijection. In fact, $f \circ f = \mathrm{id}$, so $f$ is its own inverse. Also, the cardinality of $f(A)$ is always $1$ away from the cardinality of $A$. So, $f$ maps the even-cardinality subsets to the odd-cardinality subsets, and vice versa.

In conclusion, one has $$ \sum_{k=0}^{n} \binom{2n}{2k} = \frac{\text{the number of subsets of $\{1,2,\ldots,2n\}$}}{2} = \frac{2^{2n}}{2} = 2^{2n-1}$$

share|improve this answer
    
High school me would have known this cold :|. –  Clark Kent May 8 at 22:42
    
@ClarkKent: Is your pupil a highschool student? –  Mike F May 8 at 22:45
    
He's a college student. I just used to be extremely good at combinatorics when I was in high school thanks to math olympiads. –  Clark Kent May 8 at 22:56
    
@ClarkKent: well, here's a (maybe?) fun follow-up problem for you: For what fraction of the $3^n$ maps $f : \{1,\ldots,n\} \to \{1,2,3\}$ is $\sum_{k=1}^n f(k)$ a multiple of $3$? –  Mike F May 8 at 23:35

Let me add another way of obtaining the same answer based on Pascal's Triangle. As you know, the sum of all elements of the row $a=2^a$. Take consecutive elements of row $2n-1$ and pair them off. The sum of each pair is equal to $\binom{2n}k$ for some odd $k$. The sum of $\binom{2n}k$ for all odd $k$ is equal to the sum of all these pairs, the sum of all elements of row $2n-1$, $2^{2n-1}$. The sum of $\binom{2n}k$ for all even $k$ then is simply the sum of all elements of row $2n$ minus the sum for all odd $k$.

$$2^{2n}-2^{2n-1}=2^{2n-1}$$

share|improve this answer

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.