4
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.