Prove $\sum_{i=0}^{n-1} \binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i}} = 2(1 - \frac{1}{2^{2n}}\binom{2n}{n})$

Question

How can I prove $\sum_{i=0}^{n-1} \binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i}} = 2(1 - \frac{1}{2^{2n}}\binom{2n}{n})$ without induction? I think I have to use Taylor series at some point.

Answer 1

We may notice that by setting $C_i=\frac{1}{i+1}\binom{2i}{i}$ and $A_i=\frac{C_i}{4^i}$ we have $$ f(x) = \sum_{i\geq 0}A_i x^i = 2\frac{1-\sqrt{1-x}}{x}\tag{1} $$ hence $$ \frac{f(x)}{1-x}=\sum_{i\geq 0}(A_0+\ldots+A_i)x^i = 2 \frac{1-\sqrt{1-x}}{x(1-x)} \tag{2} $$ and the wanted sum is the coefficient of $x^{n-1}$ in the RHS of $(2)$, or the coefficient of $x^n$ in $$ \frac{2}{1-x}-\frac{2}{\sqrt{1-x}}\tag{3} $$ whose Taylor series is well-known and leads to $$ \sum_{i=0}^{n-1}A_i = 2-\frac{2}{4^n}\binom{2n}{n}\tag{4} $$ as wanted.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{i = 0}^{n - 1}{2i \choose i}{1 \over i + 1}\,{1 \over 2^{2i}} & = \bracks{z^{n}}\sum_{\ell = 1}^{\infty}z^{\ell}\bracks{\sum_{i = 0}^{\ell - 1}{2i \choose i}{1 \over i + 1}\,{1 \over 2^{2i}}} = \bracks{z^{n}}\sum_{i = 0}^{\infty}{2i \choose i}{1 \over i + 1} \,{1 \over 2^{2i}}\sum_{\ell = i + 1}^{\infty}z^{\ell} \\[5mm] & = \bracks{z^{n}}\sum_{i = 0}^{\infty}{2i \choose i}{1 \over i + 1} \,{1 \over 2^{2i}}\sum_{\ell = 0}^{\infty}z^{\ell + i + 1} \\[5mm] & = \bracks{z^{n - 1}}\pars{1 - z}^{-1} \sum_{i = 0}^{\infty}\ \overbrace{{-1/2 \choose i}\pars{-4}^{i}}^{\ds{2i \choose i}}\ \pars{z \over 4}^{i}\int_{0}^{1}x^{i}\,\dd x \\[5mm] & = \bracks{z^{n - 1}}\pars{1 - z}^{-1} \int_{0}^{1}\sum_{i = 0}^{\infty}{-1/2 \choose i}\pars{-zx}^{i}\,\dd x \\[5mm] & = \bracks{z^{n - 1}}\pars{1 - z}^{-1}\int_{0}^{1}\pars{1 - zx}^{-1/2}\,\dd x \\[5mm] & = \bracks{z^{n - 1}}\pars{1 - z}^{-1}\,{2 - 2\pars{1 - z}^{1/2} \over z} \\[5mm] & = 2\bracks{z^{n}}\pars{1 - z}^{-1} - 2\bracks{z^{n}}\pars{1 - z}^{-1/2} = 2 - 2{-1/2 \choose n}\pars{-1}^{n} \\[5mm] & = 2 - 2\,{{2n \choose n} \over \pars{-4}^{n}}\,\pars{-1}^{n} = \bbx{\ds{2\bracks{1 - {1 \over 2^{2n}}{2n \choose n}}}} \end{align}

See a $\ds{{2i \choose i} = {-1/2 \choose i}\pars{-4}^{i}}$ proof in this link.