<s>[INST] Prove combination identity $ \sum_{k=0}^n {2k \choose k} {2n-2k \choose n-k} = 4^n $
I tried with mathematical induction only to fail.
Is this formula related to some special function like Beta, Gamma, etc?
 [/INST] Consider the generating function method. It is seen that for
\begin{align}
S_{n} = \sum_{k=0}^{n} \binom{2k}{k} \binom{2n-2k}{n-k} 
\end{align}
yields
\begin{align}
\sum_{n=0}^{\infty} S_{n} t^{n} &= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{2k}{k} \binom{2n-2k}{n-k} t^{n} \\
&= \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \binom{2k}{k} \binom{2n}{n} t^{n+k} \\
&= \left( \sum_{k=0}^{\infty} \binom{2k}{k} t^{k} \right)^{2} \\
&= \left( \frac{1}{\sqrt{1-4t}} \right)^{2} \\
&= \frac{1}{1-4t} \\
&= \sum_{n=0}^{\infty} 4^{n} \, t^{n}. 
\end{align}
Equating both sides yields
\begin{align}
\sum_{k=0}^{n} \binom{2k}{k} \binom{2n-2k}{n-k} = 4^{n}.
\end{align}
</s>