<s>[INST] 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)$.

 [/INST] 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$.
</s>