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? 
 A: Hint: Use the binomial theorem to compute
$$
0^{2n}=(1-1)^{2n}
$$
and
$$
2^{2n}=(1+1)^{2n}
$$
A: 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}. $$
A: 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}$$
A: 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}$$
