Proving formula sum of product of binomial coefficients

Question

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!

Answer 1

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.

Answer 2

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.