5
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ (+1) Mister Oloa, in the last equality I think we have $$\frac{1}{1-4x}=\sum_{n=0}^{\infty} 4^n x^n$$ $\endgroup$ Commented Nov 2, 2014 at 17:17
  • $\begingroup$ @Chris'ssis Typo corrected. Thank you! $\endgroup$ Commented Nov 2, 2014 at 18:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .