Algebraic proof of a combinatoric question (Combinatoric proof is given) I had a IMO training about double counting. Then, there is a problem  which I hope there is a combinatoric proof. Here comes the problem:

For every positive integer $n$, let $f\left(n\right)$ be the number of all positive integers with exactly $2n$ digits, each having exactly $n$ of digits equal to $1$ and the other equal to $2$. Let $g\left(n\right)$ be the number of all positive integers with exactly $n$ digits, each of its digits can only be $1,2,3$ or $4$ and the number of $1$'s equals the number of $2$'s. Prove that $f\left(n\right)=g\left(n\right)$.

It is obvious to see that $f\left(n\right)=\binom{2n}{n}$, and $g\left(n\right)=\sum_{k\le\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}\binom{2k}{k}2^{n-2k}$. However, it is hard to prove this in an algebraic way. I hope there are someone to prove it by algebraic way. Thank you!
Combinatoric proof

We can establish a one-to-one correspondence between $f\left(n\right)$ and $g\left(n\right)$.  Let $F\left(n\right)$ be the set of all positive integers with exactly $2n$ digits, each having exactly $n$ of digits equal to $1$ and the other equal to $2$.  Also, let $G\left(n\right)$ be the set of all positive integers with exactly $n$ digits, each of its digits can only be $1,2,3$ or $4$ and the number of $1$'s equals the number of $2$'s.  Then, we can do this operation for all numbers in $F\left(n\right)$:  For every two digits of the numbers in $F\left(n\right)$, $$\begin{cases}11\Rightarrow 1\\22\Rightarrow 2\\12\Rightarrow 3\\21\Rightarrow 4\end{cases}$$ Then all the numbers will change into a set which is totally same as $G\left(n\right)$, as we find that the difference between the number of $1$'s and $2$'s doesn't change at all.  Therefore, we make a one-to-one correspondence between $F\left(n\right)$ and $G\left(n\right)$.

 A: 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$.
A: 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.
A: 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.
A: Yet another proof:
\begin{align*}
\binom{2n}{n} 
&= [x^n](1+x)^{2n} \\
&= [x^n]((1+x^2) + 2x)^n \\
&= \sum_{j=0}^n \binom{n}{j} 2^{n-j} [x^n]\left(x^{n-j}(1+x^2)^j\right) \\
&= \sum_{j=0}^n \binom{n}{j} 2^{n-j} [x^j](1+x^2)^j \\
&= \sum_{\substack{0 \leq j \leq n \\ j \text{ even}}} \binom{n}{j} \binom{j}{j/2} 2^{n-j}
\end{align*}
I think this approach corresponds most closely to the logic of your combinatorial proof, in that we can interpret $1$ as $1$ and $2$ as $x$ in the product $(1 + x)^{2n}$, and we proceed by pairing off consecutive factors: $11 \mapsto 1$, $22 \mapsto x^2$, $12 \mapsto x$ and $21 \mapsto x$. In the first version, taking the coefficient of $x^n$ corresponds to considering the sequences with the same number of $1$'s and $2$'s, while in the second version it corresponds to considering the sequences with the same number of $11$'s and $22$'s (disregarding the $12$'s and $21$'s, i.e. the $3$'s and $4$'s).
