<s>[INST] Approaching Tricky Combinatorial Proofs - Tough Example I'm struggling with finding effective ways to approach questions (especially proofs) that use summations and Taylor Series. I've worked through several simpler examples, but always get stuck once a non-trivial question arises. In particular, I'm hoping to get some help in proving the following statement
$$\sum_{i=0}^{n-1} {2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=2(1-\frac{1}{2^{2i}}{2i \choose i})$$
As a hint, it's stated that $ \frac{1-\sqrt{1-x}}{\frac{1}{2}x}=\sum_{i=0}^{\infty}{2i \choose i}\frac{1}{i+1}\frac{x^{i}}{2^{2i}} $ and that it may potentially be necessary to derive the Taylor seires centered at $x=0$ for $\frac{1-\sqrt{1-x}}{x} $ and $\frac{1}{\sqrt{1-x}} $
With some help, I've done the following work, but am not sure if I'm either headed in the right direction, or even correct:
$$\sum_{i=0}^{n-1} {2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=\sum_{i=0}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}-\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=2-\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}$$
From here, I've tried to get to the point of proving the following:
$$2-\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=2-\frac{2}{2^n}{2n \choose n}$$
$$\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=\frac{2}{2^n}{2n \choose n} $$
I really don't know where to proceed next, or which direction the proof will continue in. Any additions/corrections would be greatly appreciated. Thank you!
Edit: to add on another potential solution, would it hold any water to try to write down a recurrence relation, assuming the left side of the first equation to be $ a_n $?
 [/INST] Here is  an approach based on the observation that
\begin{align*}
\sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\cdot\frac{1}{2^{2i}}
\end{align*}
is a Cauchy-product which can be interpreted as the coefficient of the product of two (ordinary) generating functions. We recall the generating function of the Catalan numbers $C_i=\binom{2i}{i}\frac{1}{i+1}$
\begin{align*}
C(x)=\sum_{i=0}^\infty C_i x^i=\frac{1-\sqrt{1-4x}}{2x}\tag{1}
\end{align*}
It is also convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain
  \begin{align*}
\sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i}}
&=\frac{1}{4^{n-1}}\sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}4^{n-1-i}\tag{2}\\
&=\frac{1}{4^{n-1}}[x^{n-1}]\frac{C(x)}{1-4x}\tag{3}\\
&=\frac{1}{4^{n-1}}[x^{n-1}]\frac{1-\sqrt{1-4x}}{2x(1-4x)}\tag{4}\\
&=\frac{1}{2\cdot4^{n-1}}[x^{n}]\left(\frac{1}{1-4x}-\frac{1}{\sqrt{1-4x}}\right)\tag{5}\\
&=\frac{1}{2\cdot4^{n-1}}\left(4^n-\binom{-\frac{1}{2}}{n}(-4)^n\right)\tag{6}\\
&=2\left(1-\frac{1}{2^{2n}}\binom{2n}{n}\right)\tag{7}
\end{align*}
  and the claim follows.

Comment:


*

*In (2) we write the sum as Cauchy-product in the form $\sum_{i=0}^{n-1}a_ib_{n-1-i}$.

*In (3) we use the fact that the Cauchy-product is the coefficient of $x^{n-1}$ of $C(x)$ and the geometric series $\frac{1}{1-4x}$.

*In (4) we use the representation (1).

*In (5) we do a small rearrangement to easily derive the coefficients of the series and apply the rule $[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$.

*In (6) we select the coefficient of $x^n$ of the geometric series and the binomial series with $\alpha=-\frac{1}{2}$.

*In (7) we apply the binomial identity 
\begin{align*}
\binom{-\frac{1}{2}}{i}=\frac{1}{2^{2i}}\binom{2i}{i}(-1)^i
\end{align*}
See e.g. (1.9) in H.W. Goulds Binomial Identities, vol. 1.
</s>