Evaluate $\sum_{k=0}^n {{2n + 1}\choose {2k + 1}}$ Evaluate $$ \sum_{k=0}^n {{2n + 1}\choose {2k + 1}} $$
I'm really stuck on this one, no idea how to progress. My best guess is to somehow get it into the form of $ n\choose k $ and then take that summation and work with that. Or maybe binomial theorem, but I'm very experienced with that. If you could give a breakdown on how to tackle these problems that'd be great!

Solution $1$:
$$
\sum_{k=0}^{n}\binom{2n+1}{2k+1}\stackrel{\text{Pascal's}}=\sum_{k=0}^{n}\left(\binom{2n}{2k}+\binom{2n}{2k+1}\right)=\sum_{i=0}^{2n+1}\binom{2n}i=\sum_{i=0}^{2n}\binom{2n}i=2^{2n}.
$$
Solution $2$:
The summation counts the number of odd-sized subsets of a set of size $2n+1$. Exactly half of these subsets are odd, because a set is odd if and only if its complement is even. That is, complentation is a bijection between even and odd subsets. Since there are $2^{2n+1}$ subsets total, half of which are odd, the number of odd subsets is $2^{2n}$.
