Prove by induction: $\sum_{k = 0}^n {{2n + 1}\choose{2k + 1}} = 4^n$ I'm having a hard time proving:
$$
\sum_{k = 0}^n {{2n + 1}\choose{2k + 1}} = 4^n
$$
The initial step is rather simple to prove, but I seem to miss something important in the induction step ($n \Rightarrow n + 1$). 
This is what I got so far:
$$
\begin{alignat*}{3}
&\sum_{k = 0}^{n + 1} {{2(n + 1) + 1}\choose{2k + 1}} \\
= &\sum_{k = 0}^{n + 1} {{2n + 3}\choose{2k + 1}} \\
= &\sum_{k = 0}^{n} {{2n + 3}\choose{2k + 1}} + {{2n + 3}\choose{2n + 3}} \\
= &\sum_{k = 0}^{n} {{2n + 3}\choose{2k + 1}} + 1 \\
\end{alignat*}
$$
I cannot find a way to use the induction hypothesis, since the binomial coefficient inside the sum contains the term $2n + 3$ instead of $2n + 1$. 
How can I proceed from here? Any tips?

Here's an inductive proof.
Using $\binom{a+1}{b}=\binom{a}{b}+\binom{a}{b-1}$ twice, we get:
$$\begin{align}\binom{2n+3}{2k+1}&=\binom{2n+2}{2k+1} + \binom{2n+2}{2k}\\
&=\binom{2n+1}{2k+1}+2\binom{2n+1}{2k}+\binom{2n+1}{2k-1}\\
&=\binom{2n+1}{2k+1}+2\binom{2n+1}{2(n-k)+1}+\binom{2n+1}{2k-1}
\end{align}$$
The last equality because $\binom{a}{b}=\binom{a}{a-b}$.
Now, how many times does $\binom{2n+1}{2j+1}$ occur in:
$$\sum_{k=0}^{n+1}\binom{2n+3}{2k+1}=\sum_{k=0}^{n+1}\left(\binom{2n+1}{2k+1}+2\binom{2n+1}{2(n-k)+1}+\binom{2n+1}{2k-1}\right)?$$
It occurs once when $k=j$ once when $k=j+1$ and twice when $n-k=j$.
