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)$.


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.
