Sums of central binomial coefficients

Question

Are there closed forms for $$\sum^n_{i=0} \binom{2i}{i}$$ and $$\sum^n_{i=0} \binom{2i}{i}^2$$?

Also, how can these sums be approximated?

Answer 1

What follows is unfortunately not very rigorous, but the approximations obtained do agree with the sums numerically.

We first divide out the last term of the sum, which contains most of its bulk, to get

$$ \sum^n_{i=0} \binom{2i}{i} = \binom{2n}{n} \sum^n_{k=0} \frac{\binom{2(n-k)}{n-k}}{\binom{2n}{n}}. $$

For fixed $k$ one can verify (using series expansion) that

$$ \frac{\binom{2(n-k)}{n-k}}{\binom{2n}{n}} = 4^{-k} + \frac{k4^{-k}}{2n} + O\left(\frac{1}{n^2}\right). $$

We might then expect that

$$ \begin{align} \binom{2n}{n} \sum^n_{k=0} \frac{\binom{2(n-k)}{n-k}}{\binom{2n}{n}} &= \binom{2n}{n}\left[\sum^n_{k=0} 4^{-k} + \frac{1}{2n} \sum^n_{k=0} k4^{-k} + O\left(\frac{1}{n^2}\right)\right] \\ &= \binom{2n}{n}\left[\sum_{k=0}^{\infty} 4^{-k} + \frac{1}{2n} \sum_{k=0}^{\infty} k4^{-k} + O\left(\frac{1}{n^2}\right)\right] \\ &= \binom{2n}{n}\left[\frac{4}{3} + \frac{2}{9n} + O\left(\frac{1}{n^2}\right)\right] \\ &= \frac{4}{3} \binom{2n}{n}\left[1 + \frac{1}{6n} + O\left(\frac{1}{n^2}\right)\right], \end{align} $$

where the tails of the sum have been absorbed into the $O(1/n^2)$.

Similarly,

$$ \sum_{i=0}^{n} \binom{2i}{i}^2 = \binom{2n}{n}^2 \sum_{k=0}^{n} \frac{\binom{2(n-k)}{n-k}^2}{\binom{2n}{n}^2}, $$

and

$$ \frac{\binom{2(n-k)}{n-k}^2}{\binom{2n}{n}^2} = 16^{-k} + \frac{k16^{-k}}{n} + O\left(\frac{1}{n^2}\right), $$

so

$$ \begin{align} \binom{2n}{n}^2 \sum_{k=0}^{n} \frac{\binom{2(n-k)}{n-k}^2}{\binom{2n}{n}^2} &= \binom{2n}{n}^2\left[\sum_{k=0}^{\infty} 16^{-k} + \frac{1}{n} \sum_{k=0}^{\infty} k16^{-k} + O\left(\frac{1}{n^2}\right)\right] \\ &= \binom{2n}{n}^2\left[\frac{16}{15} + \frac{16}{225n} + O\left(\frac{1}{n^2}\right)\right] \\ &= \frac{16}{15} \binom{2n}{n}^2\left[1 + \frac{1}{15n} + O\left(\frac{1}{n^2}\right)\right]. \end{align} $$

So the approximations we obtain are

$$ \sum_{i=0}^{n} \binom{2i}{i} = \frac{4}{3} \binom{2n}{n}\left[1 + \frac{1}{6n} + O\left(\frac{1}{n^2}\right)\right] $$ and $$ \sum_{i=0}^{n} \binom{2i}{i}^2 = \frac{16}{15} \binom{2n}{n}^2\left[1 + \frac{1}{15n} + O\left(\frac{1}{n^2}\right)\right] $$ as $n \to \infty$.

Answer 2

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$ $\large\tt\mbox{Hint:}$

1. \begin{align} \sum_{k = 0}^{n}{2k \choose k} &= \sum_{k = 0}^{n}\int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\, {\pars{1 + z}^{2k} \over z^{k + 1}} = \int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z} \sum_{k = 0}^{n}\bracks{\pars{1 + z}^{2} \over z}^{k} \\[3mm]&= \int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z}\, {\bracks{\pars{1 + z^{2}}/z}^{n + 1} - 1 \over \pars{1 + z^{2}}/z - 1} = \int_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n + 1}}\, {\pars{1 + z^{2}}^{n + 1} - z^{n + 1} \over z^{2} - z + 1} \\[3mm]&= {1 \over n!}\,\lim_{z \to 0}\totald[n]{}{z}\bracks{% {\pars{1 + z^{2}}^{n + 1} - z^{n + 1} \over z^{2} - z + 1}} \end{align}