4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Yes, there is, but it involves hypergeometric functions, and elliptic integrals. $\endgroup$ – Lucian Nov 19 '13 at 1:07
  • $\begingroup$ 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. $\endgroup$ – Antonio Vargas Nov 19 '13 at 18:42
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.