Algebraic proof of a combinatoric question (Combinatoric proof is given)

Here is the generating function approach: \begin{align} \sum_{n=0}^\infty \left(\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\binom{2k}{k} 2^{n-2k}\right) z^n &= \sum_{k=0}^\infty \binom{2k}{k} 2^{-2k} \sum_{n=2k}^\infty \binom{n}{2k}(2z)^n \\ &= \sum_{k=0}^\infty \binom{2k}{k} 2^{-2k} \frac{(2z)^{2k}}{(1-2z)^{2k+1}} \\ &= \frac{1}{1-2z} \sum_{k=0}^\infty \binom{2k}{k} \left[\left(\frac{z}{1-2z}\right)^2\right]^k \\ &= \frac{1}{1-2z} \cdot \frac{1}{\sqrt{1-4(z/(1-2z))^2}} \\ &= \frac{1}{\sqrt{1-4z}} \\ &= \sum_{n=0}^\infty \binom{2n}{n}z^n. \end{align} Hence $$\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\binom{2k}{k} 2^{n-2k} = \binom{2n}{n}$$ for all $n$.

Claim 2 in the second solution to Exercise 2 from Fall 2018 UMN Math 5705 homework set #2 states the following:

Claim 2: Let $n \in \mathbb N$ and $u \in \mathbb Z$. Then, \begin{align} \sum_{k=0}^n 2^{n-2k-u} \dbinom{n}{2k+u} \dbinom{2k+u}{k} = \dbinom{2n}{n+u} . \end{align}

Your identity is a particular case of this when $u$ is taken to be $0$.

Claim 2 is also Theorem 2 in https://artofproblemsolving.com/community/c6h87265 , but the version of the proof in my homework set is better IMHO. Either way, the algebraic proof proceeds by induction on $n$, with the induction step being chiefly about rewriting $\dbinom{n+1}{2k+u}$ as $\dbinom{n}{2k+u-1} + \dbinom{n}{2k+u}$, then doing the same with $\dbinom{2k+u}{k}$ in one of the resulting sums, and a couple more such transformations at the very end when it comes to collecting terms. It is a completely unremarkable computation.

Here is a slightly different proof that

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

We observe that

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

We get for our sum

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

Now when $2k\gt n$ we get zero from the coefficient extractor, which enforces the range, so we continue with

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

This is the claim.