<s>[INST] Proving formula sum of product of binomial coefficients I have to proof the following formula
\begin{align}
\sum_{k=0}^{n/2} {n\choose2k} {2k\choose k} 2^{n-2k} = {2n\choose n}
\end{align}
I tried to use the fact that ${2n\choose n} = \sum_{k=0}^{n} {n\choose k}^2$, but I don't get any conclusion. Any suggestions? Thanks in advance! 
 [/INST] Starting from
$$\sum_{k=0}^{\lfloor n/2 \rfloor}
{n\choose 2k} {2k\choose k} 2^{n-2k}$$
we write
$${n\choose 2k} {2k\choose k} =
\frac{n!}{(n-2k)! \times k! \times k!}
= {n\choose k} {n-k\choose k}$$
to obtain
$$\sum_{k=0}^{\lfloor n/2 \rfloor}
{n\choose k} 2^{n-2k} {n-k\choose n-2k}
\\ = \sum_{k=0}^{\lfloor n/2 \rfloor}
{n\choose k} 2^{n-2k} [z^{n-2k}] (1+z)^{n-k}
\\ = [z^n] \sum_{k=0}^{\lfloor n/2 \rfloor} 
{n\choose k} z^{2k} (1+z)^{n-k} 2^{n-2k}.$$
Now  when  $2k\gt n$  there  is  no  contribution to  the  coefficient
extractor and we may write
$$ [z^n] 2^n (1+z)^n \sum_{k\ge 0}
{n\choose k} z^{2k} (1+z)^{-k} 2^{-2k}
\\ = [z^n] 2^n (1+z)^n  (1+z^2/(1+z)/2^2)^n
\\ = \frac{1}{2^n} [z^n] (2^2+2^2z+z^2)^n
= \frac{1}{2^n} [z^n] (z+2)^{2n}
= \frac{1}{2^n} {2n\choose n} 2^n = {2n\choose n}.$$
This is the claim.
</s>