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! 
 A: Define the following two sets:
$$\mathcal{A} = \{ x \in \{0, 1, 2, 3\}^n : \mbox{a number of $1$'s in $x$ and a number of $0$'s in $x$ are the same} \}.$$
$$\mathcal{B} = \{ y\in\{0, 1\}^{2n} : \mbox{there are $n$ ones in $y$} \}.$$
Note that $|\mathcal{A}|$ equals the left hand side  and $|\mathcal{B}|$ equals the right hand side. All that remains to do is to come up with a bijection between $\mathcal{A}$ and $\mathcal{B}$.
Define the following mapping
$$\phi : \mathcal{A} \to \mathcal{B},$$
$$\phi(x_1\ldots x_n) = \psi(x_1)\ldots \psi(x_n),$$
where $\psi$ is a mapping from $\{0, 1, 2, 3\}$ to $\{0, 1\}^2$, defined as follows
$$\psi(0) = 00, \psi(1) = 11, \psi(2) = 01, \psi(3) = 10.$$
It's obvious that $\phi$ is bijective. To show it formally  you just have to notice the following thing. Take any $y\in\{0, 1\}^{2n}$. Split $y$ into $n$ blocks of 2 consecutive bits. Then $y\in\mathcal{B}$ iff a number of $00$-blocks and a number of $11$-blocs are the same. 
A: 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.
