<s>[INST] Show that $\sum_{\ell=0}^k \binom{2k+1}{2\ell} = 2^{2k}$ In acquainting myself with the Cauchy product, I am trying to derive the power series of $\sin(x)\cos(x)$. Of course, $\sin(x)\cos(x)=\frac12\sin(2x)$ is easy to work with so I know what to expect.
We have
$$\sin(x) = \sum_{n=0}^\infty \frac{(-1)^n}{(2n+1)!} x^{2n+1} \implies \frac12\sin(2x) = \sum_{n=0}^\infty \frac{(-1)^n}{(2n+1)!} 2^{2n} x^{2n+1}$$
Then the Cauchy product is
$$\begin{align*}
\sin(x)\cos(x) &= \sum_{k=0}^\infty \sum_{\ell=0}^k \frac{(-1)^\ell}{(2\ell)!} \frac{(-1)^{k-\ell}}{(2(k-\ell)+1)!} x^{2k+1} \\
&= \sum_{k=0}^\infty (-1)^k x^{2k+1} \sum_{\ell=0}^k \frac1{(2\ell)! (2k-2\ell+1)!} \\
&= \sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)!} x^{2k+1} \sum_{\ell=0}^k \binom{2k+1}{2\ell}
\end{align*}$$
and the titular identity follows. How can one prove it?
Induction is a bit tricky. We have
$$\begin{align*}
\sum_{\ell=0}^{k+1} \binom{2k+3}{2\ell} &= \binom{2k+3}0 + \sum_{\ell=1}^k \binom{2k+3}{2\ell} + \binom{2k+3}{2k+2} \\[1ex]
&= 2k+4 + \sum_{\ell=1}^k \left[\binom{2k+1}{2\ell-2} + 2 \binom{2k+1}{2\ell-1} + \binom{2k+1}{2\ell}\right] \\[1ex]
&= 2^{2k} + 2k+3 + \sum_{\ell=1}^k \left[\binom{2k+1}{2\ell-2} + 2 \binom{2k+1}{2\ell-1}\right]
\end{align*}$$
but I'm not sure where to go from here. Any other suggestions/methods are appreciated.
 [/INST] Hint: Since $\dbinom{2k+1}{2\ell} = \dbinom{2k+1}{2k+1-2\ell}$, the sum (which we'll denote by $S$) satisfies:
\begin{align*}
S &= \dbinom{2k+1}{0}+\dbinom{2k+1}{2}+\cdots+\dbinom{2k+1}{2k-2}+\dbinom{2k+1}{2k}
\\
S &= \dbinom{2k+1}{2k+1}+\dbinom{2k+1}{2k-1}+\cdots+\dbinom{2k+1}{3}+\dbinom{2k+1}{1}
\end{align*}
Now, add these two equations together and see what you get.
</s>