How can we prove the identity $\sum_{r=0, r~ even}^{k}\binom{k}{r}\binom{r}{r/2}2^{k-r}=\binom{2k}{k}$?

Question

We know that $$\sum_{r=0}^{k}{\binom{k}{r}}^2=\binom{2k}{k}$$ Can we prove such identity for the above case. I can check the identity for some numerical values. For example $k=4$ case satisfies it.

Answer 1

We're going to using $2$ ways to calculate the coefficient of $x^k$ in $(1+x)^{2k}$.

First, the binomial formula suggests it's $\binom{2k}{k}$

And notice $$(1+x)^{2k}=(1+2x+x^2)^k=\sum_{m+n+l=k} { k\choose m,n,l}(2x)^n(x^2)^l $$

This indicates the coefficients are $$\sum_{m+n+l=k\\n+2l=k} { k\choose m,n,l }2^n=\sum_{\;r=0\\ r\;\text{even}}\binom{k}{r}\binom{r}{r/2}2^{k-r} $$

It completes our proof.

Answer 2

We seek to prove the identity

$$\sum_{q=0}^{\lfloor n/2\rfloor} {n\choose 2q} {2q\choose q} 2^{n-2q} = {2n\choose n}.$$

We have

$${n\choose 2q} {2q\choose q} = \frac{n!}{(n-2q)! \times q! \times q!} = {n\choose q} {n-q\choose n-2q}.$$

The LHS is

$$\sum_{q=0}^{\lfloor n/2\rfloor} {n\choose q} {n-q\choose n-2q} 2^{n-2q} = 2^n [z^n] (1+z)^n \sum_{q=0}^{\lfloor n/2\rfloor} {n\choose q} z^{2q} (1+z)^{-q} 2^{-2q}.$$

Here the coefficient extractor enforces the upper limit of the sum and we obtain

$$2^n [z^n] (1+z)^n \sum_{q\ge 0} {n\choose q} z^{2q} (1+z)^{-q} 2^{-2q} \\ = 2^n [z^n] (1+z)^n \left(1+\frac{z^2}{4(1+z)}\right)^n = 2^n [z^n] \left(1+z+\frac{z^2}{4}\right)^n \\ = 2^n [z^n] \left(1+\frac{z}{2}\right)^{2n} = 2^n {2n\choose n} \frac{1}{2^n} = {2n\choose n}.$$

This sum also appeared at the following MSE link.

Addendum. In hindsight we may simplify this starting from

$${2n\choose n} = [z^n] (1+z)^{2n} = [z^n] (1+2z+z^2)^n = [z^n] \sum_{q=0}^n {n\choose q} z^q (2+z)^q \\ = \sum_{q=0}^n {n\choose q} [z^{n-q}] (2+z)^q = \sum_{q=0}^n {n\choose q} {q\choose n-q} 2^{2q-n} \\ = \sum_{q=0}^n {n\choose q} {n-q\choose q} 2^{n-2q} = \sum_{q=0}^n {n\choose q} {n-q\choose n-2q} 2^{n-2q}.$$

This is what the first answer to appear used.