mjhjmtu

I have to proof the following formula
beginalign
sum_k=0^n/2 nchoose2k 2kchoose k 2^n-2k = 2nchoose n
endalign

I tried to use the fact that $2nchoose n = sum_k=0^n nchoose k^2$, but I don't get any conclusion. Any suggestions? Thanks in advance!

Starting from

$$sum_k=0^lfloor n/2 rfloor
nchoose 2k 2kchoose k 2^n-2k$$

we write

$$nchoose 2k 2kchoose k =
fracn!(n-2k)! times k! times k!
= nchoose k n-kchoose k$$

to obtain

$$sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k n-kchoose n-2k
\ = sum_k=0^lfloor n/2 rfloor
nchoose k 2^n-2k [z^n-2k] (1+z)^n-k
\ = [z^n] sum_k=0^lfloor n/2 rfloor
nchoose k z^2k (1+z)^n-k 2^n-2k.$$

Now when $2kgt n$ there is no contribution to the coefficient
extractor and we may write

$$ [z^n] 2^n (1+z)^n sum_kge 0
nchoose k z^2k (1+z)^-k 2^-2k
\ = [z^n] 2^n (1+z)^n (1+z^2/(1+z)/2^2)^n
\ = frac12^n [z^n] (2^2+2^2z+z^2)^n
= frac12^n [z^n] (z+2)^2n
= frac12^n 2nchoose n 2^n = 2nchoose n.$$

This is the claim.

Define the following two sets:
$$mathcalA = x in 0, 1, 2, 3^n : mboxa number of $1$'s in $x$ and a number of $0$'s in $x$ are the same .$$

$$mathcalB = yin0, 1^2n : mboxthere are $n$ ones in $y$ .$$

Note that $|mathcalA|$ equals the left hand side and $|mathcalB|$ equals the right hand side. All that remains to do is to come up with a bijection between $mathcalA$ and $mathcalB$.

Define the following mapping
$$phi : mathcalA to mathcalB,$$
$$phi(x_1ldots 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 $yin0, 1^2n$. Split $y$ into $n$ blocks of 2 consecutive bits. Then $yinmathcalB$ iff a number of $00$-blocks and a number of $11$-blocs are the same.