combinatorics - 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 $?

Answer

We are interested in verifying that

$$S_n = \sum_{q=0}^n {2q\choose q}\frac{1}{q+1}\frac{1}{2^{2q}}
= 2 - \frac{1}{2^{2n}} {2n+1\choose n+1}.$$

Now we recognize the Catalan numbers here where

$$C(z) = \sum_{q\ge 0} {2q\choose q}\frac{1}{q+1} z^q

= \frac{1-\sqrt{1-4z}}{2z}.$$

We then have from first principles that the sum is given by

$$S_n =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} C(z/4)\; dz.$$

Now recall the functional equation (e.g. from combinatorial species)
of $C(z)$ which is

$$C(z) = 1 + z C(z)^2$$

which means that with $D(z) = C(z/4)$ we obtain

$$D(z) = 1 + z D(z)^2/4.$$

Recall that our integral is

$$S_n =

\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} D(z)\; dz.$$

We have that $$z = \frac{4D(z) - 4}{D(z)^2}
= 4\frac{1}{D(z)} - 4\frac{1}{D(z)^2}$$

so in putting $w=D(z)$ we get

$$dz = \left(-4\frac{1}{w^2} + 8\frac{1}{w^3} \right) \; dw$$

which yields for the integral (we have $D(0) = 1$ as can be seen from
the series)

$$S_n =
\frac{1}{2\pi i}
\int_{|w-1|=\gamma} \frac{w^{2n+2}}{4^{n+1} (w-1)^{n+1}}
\frac{1}{1-4/w+4/w^2}
\\ \times w \left(-4\frac{1}{w^2} + 8\frac{1}{w^3} \right) \; dw
\\ = \frac{1}{2\pi i}
\int_{|w-1|=\gamma} \frac{w^{2n+5}}{4^{n+1} (w-1)^{n+1}}

\frac{1}{w^2-4w+4}
\\ \times \left(-4\frac{1}{w^2} + 8\frac{1}{w^3} \right) \; dw
\\ = \frac{1}{2\pi i}
\int_{|w-1|=\gamma} \frac{w^{2n+2}}{4^{n+1} (w-1)^{n+1}}
\frac{1}{(w-2)^2}
\left(-4w + 8\right) \; dw
\\ = \frac{1}{4^n} \frac{1}{2\pi i}
\int_{|w-1|=\gamma} \frac{w^{2n+2}}{(w-1)^{n+1}}
\frac{1}{1-(w-1)} \; dw.$$

The integral and the scalar in front are

$$\frac{1}{4^n} [(w-1)^{n}] \frac{1}{1-(w-1)}
\sum_{q=0}^{2n+2} {2n+2\choose q} (w-1)^q
\\ = \frac{1}{4^n} \sum_{q=0}^{n} {2n+2\choose q}
[(w-1)^{n-q}] \frac{1}{1-(w-1)}
= \frac{1}{2^{2n}} \sum_{q=0}^{n} {2n+2\choose q}
\\ = \frac{1}{2^{2n+1}} \left(2^{2n+2} - {2n+2\choose n+1}\right).$$

where the last step was by inspection. We thus get for the closed

form

$$\bbox[5px,border:2px solid #00A000]{
2 - \frac{1}{2^{2n+1}} {2n+2\choose n+1}.}$$

Observe that this is

$$2 - \frac{1}{2^{2n+1}} \frac{2n+2}{n+1} {2n+1\choose n}
= 2 - \frac{1}{2^{2n}} {2n+1\choose n}
= 2 - \frac{1}{2^{2n}} {2n+1\choose n+1}$$

which is the form presented in the introduction. It would be
interesting to see a formal power series only proof of this which
would have to have certain features distinguishing it from the above,
where we used the differential in the integral.

Remark. Induction is the simplest here, we get

$$2 - \frac{1}{2^{2n}} {2n+1\choose n+1}
+ {2n+2\choose n+1} \frac{1}{n+2}\frac{1}{2^{2n+2}}

\\ = 2 - \frac{1}{2^{2n}} {2n+1\choose n+1}
+ {2n+3\choose n+2} \frac{1}{2n+3}\frac{1}{2^{2n+2}}
\\ = 2 - \frac{1}{2^{2n}} {2n+2\choose n+2} \frac{n+2}{2n+2}
+ {2n+3\choose n+2} \frac{1}{2n+3}\frac{1}{2^{2n+2}}
\\ = 2 - \frac{1}{2^{2n}} {2n+3\choose n+2}
\frac{n+1}{2n+3} \frac{n+2}{2n+2}
+ {2n+3\choose n+2} \frac{1}{2n+3}\frac{1}{2^{2n+2}}.$$

Now

$$4 \frac{n+1}{2n+3} \frac{n+2}{2n+2} - \frac{1}{2n+3}
= 1$$

and we obtain

$$2 - \frac{1}{2^{2n+2}} {2n+3\choose n+2}$$

which is the desired result. (Observe that $S_1 = 1 + \frac{1}{4} = 2
- \frac{1}{4} {3\choose 2}.$)