1. How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ?

  2. Does anyone know any better elementary estimates?

  • 2
    $\begingroup$ For (2), Stirling's approximation yields ${2n\choose n}\sim (\pi n)^{-1/2} 4^n$, and you might look at some of the other formulas for sharper bounds. $\endgroup$ – anon Aug 19 '11 at 20:49
  • 1
    $\begingroup$ @anon The Central Limit Theorem shows that eventually the Stirling approximation must be an upper bound (and it actually is for all positive $n$). A lower bound is obtained the same way by multiplying the upper bound by $\exp(-1/(4n))$. Because this is $1 + O(1/n)$ for large $n$, it's better than the OP's bounds whose ratio equals $O(\sqrt{4/3})$. $\endgroup$ – whuber Aug 19 '11 at 20:55
  • $\begingroup$ en.wikipedia.org/wiki/Central_binomial_coefficient $\endgroup$ – yoyo Aug 19 '11 at 21:06
  • $\begingroup$ @whuber: 1,000,000=O(sqrt(4/3)). en.wikipedia.org/wiki/Big_O_notation#Formal_definition $\endgroup$ – Did Aug 20 '11 at 12:32

Here are some crude bounds:

$${1\over 2\sqrt{n}}\leq {2n\choose n}{1\over 2^{2n}}\leq{3\over4\sqrt{n+1}},\quad n\geq1.$$

We begin with the product representations $${2n\choose n}{1\over 2^{2n}}={1\over 2n}\prod_{j=1}^{n-1}\left(1+{1\over 2j}\right)=\prod_{j=1}^n\left(1-{1\over2j}\right),\quad n\geq1.$$

From $$ \prod_{j=1}^{n-1}\left(1+{1\over 2j}\right)^{\!\!2}=\prod_{j=1}^{n-1}\left(1+{1\over j}+{1\over 4j^2}\right)\geq \prod_{j=1}^{n-1}\left(1+{1\over j}\right)=n,$$ we see that $$\left({2n\choose n}{1\over 2^{2n}} \right)^{2} = {1\over (2n)^2}\, \prod_{j=1}^{n-1}\left(1+{1\over 2j}\right)^{\!\!2} \geq {1\over 4n^2}\, n ={1\over 4n},\quad n\geq1.$$ so by taking square roots, ${2n\choose n}{1\over 2^{2n}}\geq \displaystyle{1\over 2\sqrt{n}}.$

On the other hand, $$ \prod_{j=1}^{n}\left(1+{1\over 2j}\right) \left(1-{1\over 2j}\right) = \prod_{j=1}^{n}\left(1-{1\over 4j^2}\right)\leq {3\over 4},$$ so that (using the lower bound above), we have $$ {2n\choose n}{1\over 2^{2n}}=\prod_{j=1}^n\left(1-{1\over2j}\right)\leq{3\over4\sqrt{n+1}}.$$

Alternatively, multiplying the different representations we get $$n\left[{2n\choose n}{1\over 2^{2n}}\right]^2={1\over 2}\prod_{j=1}^{n-1}\left(1-{1\over4j^2}\right) \,\left(1-{1\over 2n}\right).$$ It's not hard to show that the right hand side increases from $1/4$ to $1/\pi$ for $n\geq 1$.

Edit: You can get better bounds if you know Wallis's formula:

$$2n\left[{2n\choose n}{1\over 4^n}\right]^2={1\over 2}{3\over 2}{3\over 4}{5\over 4}\cdots {2n-1\over 2n-2}{2n-1\over 2n}={1\over 2}\prod_{j=2}^n\left(1+{1\over 4j(j-1)}\right)$$

$$(2n+1)\left[{2n\choose n}{1\over 4^n}\right]^2={1\over 2}{3\over 2}{3\over 4}{5\over 4}\cdots {2n-1\over 2n-2}{2n-1\over 2n}{2n+1\over 2n}=\prod_{j=1}^n\left(1-{1\over 4j^2}\right)$$

By Wallis's formula, both middle expressions converge to ${2\over \pi}$. The right hand side of the first equation is increasing, while the right hand side of the second equation is decreasing. We conclude that

$${1\over\sqrt{\pi(n+1/2)}}\leq {2n\choose n}{1\over 4^n}\leq {1\over\sqrt{\pi n}}.$$


For $n\ge0$, we have (by cross-multiplication) $$ \begin{align} \left(\frac{n+\frac12}{n+1}\right)^2 &=\frac{n^2+n+\frac14}{n^2+2n+1}\\ &\le\frac{n+\frac13}{n+\frac43}\tag{1} \end{align} $$ Therefore, $$ \begin{align} \frac{\binom{2n+2}{n+1}}{\binom{2n}{n}} &=4\frac{n+\frac12}{n+1}\\ &\le4\sqrt{\frac{n+\frac13}{n+\frac43}}\tag{2} \end{align} $$ Inequality $(2)$ implies that $$ \boxed{\bbox[5pt]{\displaystyle\binom{2n}{n}\frac{\sqrt{n+\frac13}}{4^n}\text{ is decreasing}}}\tag{3} $$ For $n\ge0$, we have (by cross-multiplication) $$ \begin{align} \left(\frac{n+\frac12}{n+1}\right)^2 &=\frac{n^2+n+\frac14}{n^2+2n+1}\\ &\ge\frac{n+\frac14}{n+\frac54}\tag{4} \end{align} $$ Therefore, $$ \begin{align} \frac{\binom{2n+2}{n+1}}{\binom{2n}{n}} &=4\frac{n+\frac12}{n+1}\\ &\ge4\sqrt{\frac{n+\frac14}{n+\frac54}}\tag{5} \end{align} $$ Inequality $(5)$ implies that $$ \boxed{\bbox[5pt]{\displaystyle\binom{2n}{n}\frac{\sqrt{n+\frac14}}{4^n}\text{ is increasing}}}\tag{6} $$ Note that the formula in $(3)$, which is decreasing, is bigger than the formula in $(6)$, which is increasing. Their ratio tends to $1$; therefore, they tend to a common limit, $L$.

Theorem $1$ from this answer says $$ \lim_{n\to\infty}\frac{\sqrt{\pi n}}{4^n}\binom{2n}{n}=1\tag{7} $$ which means that $$ \begin{align} L &=\lim_{n\to\infty}\frac{\sqrt{n}}{4^n}\binom{2n}{n}\\ &=\frac1{\sqrt\pi}\tag8 \end{align} $$ Combining $(3)$, $(6)$, and $(8)$, we get $$ \boxed{\bbox[5pt]{\displaystyle\frac{4^n}{\sqrt{\pi\!\left(n+\frac13\right)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi\!\left(n+\frac14\right)}}}}\tag9 $$

Assymptotic Observation

If we know that $n\ge n_0$, we can replace $\frac13$ in $(1)-(3)$ and $(9)$ by $\frac14+\frac1{16n_0+12}$. Thus, asymptotically, $$ \boxed{\bbox[5pt]{\displaystyle\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi\!\left(n+\frac14\right)}}}}\tag{10} $$

  • $\begingroup$ @ByronSchmuland: Thanks! I came up with the idea of the estimates $(3)$ and $(6)$ while working on this answer, then expanded on it when I found this question. $\endgroup$ – robjohn Sep 16 '14 at 15:05
  • $\begingroup$ For finite $n$, you can use $0<O(\frac 1 {n^2})<\frac 1{72n}$ in $(11)$ (per Wikipedia). $\endgroup$ – A.S. Feb 23 '16 at 17:36
  • $\begingroup$ @robjohn: +1 as far as I know, (10) gives the sharpest upper and lower bounds. Is there a reference so we can cite? Or you may write a note and put it in arXiv.org so we can site. $\endgroup$ – Shiyu Mar 1 '16 at 19:38
  • $\begingroup$ @robjohn, I'd appreciate a reference to cite too. +1 $\endgroup$ – MikeY Dec 6 '17 at 14:40
  • $\begingroup$ @MikeY: unfortunately, this was all done for this question. I don't have any other reference other than this answer. You can get a citation from the "cite" option in the same area as the "share" and "flag" options, below the answer. $\endgroup$ – robjohn Dec 6 '17 at 14:57

You can get an even more precise answer than those already provided by using more terms in the Stirling series. Doing so yields, to a relative error of $O(n^{-5})$,

$$\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \left(1 - \frac{1}{8n} + \frac{1}{128n^2} + \frac{5}{1024n^3} - \frac{21}{32768 n^4} + O(n^{-5})\right).$$

To the same relative error of $O(n^{-5})$, the Stirling series is $$n!=\sqrt{2\pi n}\left({n\over e}\right)^n \left( 1 +{1\over12n} +{1\over288n^2} -{139\over51840n^3} -{571\over2488320n^4} + O(n^{-5}) \right).$$

Then we have $$\binom{2n}{n} = \frac{(2n)!}{n! n!} = \frac{4^n}{\sqrt{\pi n}} \frac{1 + \frac{1}{12(2n)} + \frac{1}{288(2n)^2} - \frac{139}{51840(2n)^3} - \frac{571}{2488320(2n)^4} + O(n^{-5})}{\left(1 + \frac{1}{12n} + \frac{1}{288n^2} - \frac{139}{51840n^3} - \frac{571}{2488320n^4} + O(n^{-5})\right)^2}.$$

Crunching through the long division with the polynomial in $\frac{1}{n}$ (which Mathematica can do immediately with the command Series[expression, {n, ∞, 4}]) yields the expression for $\binom{2n}{n}$ at the top of the post.

See also Problem 9.60 in Concrete Mathematics (2nd edition).

  • $\begingroup$ $\displaystyle\frac{4^n}{\sqrt{\pi n}}\left(1-\frac1{8n}+O\left(\frac1{n^2}\right)\right)$ matches the upper bound gotten in my answer. I remember computing this asymptotic series at one point. (+1) $\endgroup$ – robjohn Sep 16 '14 at 10:38

A way to get explicit bounds via Stirling's approximation is to use the following more precise formulation: $$n! = \sqrt{2\pi n} \left( \frac{n}{e} \right)^n e^{\alpha_n} $$ where $ \frac{1}{12n+1} < \alpha_n < \frac{1}{12n} $.

With this one arrives at $$ \binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} e^{\lambda_n} $$ where $ \frac{1}{24n+1} - \frac{1}{6n} < \lambda_n < \frac{1}{24n} - \frac{2}{12n+1} $.

  • $\begingroup$ @ThomasAndrews Ahh yes thank you for pointing that out. $\endgroup$ – Ragib Zaman Mar 14 '13 at 0:21

$$\binom {2n} n = \frac {2^{n-1}} n \sum _{k=0} ^{2n} \left( 1 + \cos \frac {k \pi} n \right) ^n$$


$\binom{2p}{p}$ central binomial coefficient

$$ \binom{2p}{p}=\frac{\displaystyle2^{2p}}{\displaystyle1+\sum_{n=1}^p\frac{2^n}S} $$

with $S=\sum\limits_{k=1}^{2n}\left(1+\cos\left(\frac{k\pi}n\right)\right)^n$

this new formula as the first uses a trigonometric form (see mar20 at19:11) it's more complex but gives the same result

with my pocket computer casio pb 700 I have found $\binom{2p}{p}$ exact untill

$p=18$ it's $9075135300$ after the result is given $A\cdot10^x$

example $\binom{40}{20}=1.378465288\times10^{11}$

  • $\begingroup$ I have applied MathJax. Please make sure everything is as intended. MathJax makes things easier to read. $\endgroup$ – robjohn Mar 31 '16 at 9:38

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.