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