# 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!

## 2 Answers

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.

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.