# closed form for combinatorial sum

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?

-
Sure, it is half the sum of all. –  André Nicolas May 8 '14 at 20:20
It's $2^{2n-1}$. –  Lucian May 8 '14 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 '14 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 '14 at 2:23
@Lucian That's because we usually start counting from ONE. Thanks. –  Felix Marin Jul 13 '14 at 3:20

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

-
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 '14 at 20:22
@ClarkKent: it's one of those things that once you see it, you'll never forget it :-) –  robjohn May 8 '14 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}.$$

-

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}$$

-
High school me would have known this cold :|. –  Clark Kent May 8 '14 at 22:42
@ClarkKent: Is your pupil a highschool student? –  Mike F May 8 '14 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 '14 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 '14 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}$$

-