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$
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
    $\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$ – user 1591719 Nov 2 '14 at 17:17
  • $\begingroup$ @Chris'ssis Typo corrected. Thank you! $\endgroup$ – Olivier Oloa Nov 2 '14 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.