# Sums of central binomial coefficients

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?

• Yes, there is, but it involves hypergeometric functions, and elliptic integrals. – Lucian Nov 19 '13 at 1:07
• Some naive approximateions are $$\frac{4}{3}{2n \choose n}\left[1+\frac{1}{6n} + O\left(\frac{1}{n^2}\right)\right]$$ for the first sum and $$\frac{16}{15} {2n \choose n}^2 \left[1 + \frac{1}{15n} + O\left(\frac{1}{n^2}\right)\right]$$ for the second. – Antonio Vargas Nov 19 '13 at 18:42

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$.

$\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}