Evaluate $\sum_{k=0}^n {{2n + 1}\choose {2k + 1}}$

Hint:

By applying Binomial Theorem to $ (1-1)^{2n+1}=0 $, we have:

$$ \binom{2n+1}{0}-\binom{2n+1}{1}+\binom{2n+1}{2}-\cdots+\binom{2n+1}{2n}-\binom{2n+1}{2n+1}=0 .$$

Move the negative terms to the right-hand side, we have:

$$ \binom{2n+1}{1}+\binom{2n+1}{3}+\cdots+\binom{2n+1}{2n+1}=\binom{2n+1}{0}+\binom{2n+1}{2}+\cdots+\binom{2n+1}{2n} .\tag{A}$$ And applying Binomial Theorem to $ (1+1)^{2n+1}=2^{2n+1} $, we have: $$ \binom{2n+1}{0}+\binom{2n+1}{1}+\binom{2n+1}{2}+\cdots+\binom{2n+1}{2n}+\binom{2n+1}{2n+1}=2^{2n+1} .\tag{B}$$

Further hint:

$$ 2\times (A)=(B) .$$

Hint:

$$2\sum_{k=0}^n\binom{2n+1}{2k+1}a^{2n-2k}b^{2k+1}=(a+b)^{2n+1}-(a-b)^{2n+1}=?$$

Set $a=b=1$

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