what is the summation of such a finite sequence?

Question

The summation is: $$\sum_{i=0}^n \binom{2i}i \binom{2n-2i}{n-i}$$ The answer is $4^n$. How to prove it, and how to think out it?

Answer 1

Hint. This sum may be obtained by a Cauchy product.

Recall that $$ \sum_{i=0}^n \binom{2i}i x^i=\frac{1}{\sqrt{1-4x}},\quad |x|<\frac14. \tag1 $$ (for a proof, you may use the generalized binomial theorem). Then, by the Cauchy product:

$$ \begin{align} \left(\sum_{n=0}^{\infty} \binom{2n}n x^n\right)^2 &=\sum_{n=0}^{\infty}\left( \sum_{i=0}^n \binom{2i}i \binom{2n-2i}{n-i}\right)x^n \end{align}, \quad |x|<\frac14 \tag2 $$ on the other hand, using $(1)$: $$ \begin{align} \left(\sum_{n=0}^{\infty} \binom{2n}n x^n\right)^2 =\frac{1}{1-4x}=\sum_{n=0}^{\infty} 4^n x^n ,\quad |x|<\frac14, \tag3 \end{align} $$ you just identify the coefficients in $(2)$ and $(3)$ to obtain your identity.