Prove combination identity

Question

$ \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?

Answer 1

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}