A Finite Combinatorial Sum

Question

It can be proved by induction or telescoping sum that $$\sum_{i=0}^n {2i\choose i}\frac{1}{2^{2i}}=(2n+1){2n\choose n}\frac{1}{2^{2n}}.$$ However, without knowing the right hand side in advance, I would like to know how one can evaluate the sum on the left hand side, using perhaps generating functions or other means.

Answer 1

The ogf of the left side is

$$ \sum_{n=0}^\infty \sum_{i=0}^n {2i \choose i} \dfrac{x^n}{2^{2i}}$$ Interchange the order of summation: $\sum_{n=0}^\infty \sum_{i=0}^n = \sum_{i=0}^\infty \sum_{n = i}^\infty$, and you get

$$ (1-x)^{-1} \sum_{i=0}^\infty {2i \choose i} (x/4)^i = \dfrac{1}{(1-x)^{3/2}} $$

Now use the binomial series.