# Elementary central binomial coefficient estimates

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 ?
1. Does anyone know any better elementary estimates?

Attempt. We have $$\frac1{2^n}\binom{2n}{n}=\prod_{k=0}^{n-1}\frac{2n-k}{2(n-k)}=\prod_{k=0}^{n-1}\left(1+\frac{k}{2(n-k)}\right).$$ Then we have $$\left(1+\frac{k}{2(n-k)}\right)>\sqrt{1+\frac{k}{n-k}}=\frac{\sqrt{n}}{\sqrt{n-k}}.$$ So maybe, for the lower bound, we have $$\frac{n^{\frac{n}{2}}}{\sqrt{n!}}=\prod_{k=0}^{n-1}\frac{\sqrt{n}}{\sqrt{n-k}}>\frac{2^n}{\sqrt{4n}}.$$ By Stirling, $$n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$, so the lhs becomes $$\frac{e^{\frac{n}{2}}}{(2\pi n)^{\frac14}},$$ but this isn't $$>\frac{2^n}{\sqrt{4n}}$$.

• 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.
– anon
Commented Aug 19, 2011 at 20:49
• @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})$. Commented Aug 19, 2011 at 20:55
• en.wikipedia.org/wiki/Central_binomial_coefficient
– yoyo
Commented Aug 19, 2011 at 21:06
• @whuber: 1,000,000=O(sqrt(4/3)). en.wikipedia.org/wiki/Big_O_notation#Formal_definition
– Did
Commented Aug 20, 2011 at 12:32
• I believe that you can find better estimates in the papers "Tikhonov, I. V.; Sherstyukov, V. B.; Tsvetkovich, D. G. Comparative analysis of two-sided estimates of the central binomial coefficient. Chelyab. Fiz.-Mat. Zh. 5 (2020), no. 1, 70-95; available online at doi.org/10.24411/2500-0101-2020-15106." and "Popov, A. Yu. Two-sided estimates of the central binomial coefficient. Chelyab. Fiz.-Mat. Zh. 5 (2020), no. 1, 56-69; available online at doi.org/10.24411/2500-0101-2020-15105." Commented Sep 14, 2021 at 4:43

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\ge n_0\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+\frac14+\frac1{16n_0+12}}{n+\frac54+\frac1{16n_0+12}}\tag1 \end{align} Therefore, \begin{align} \frac{\binom{2n+2}{n+1}}{\binom{2n}{n}} &=4\frac{n+\frac12}{n+1}\\ &\le4\sqrt{\frac{n+\frac14+\frac1{16n_0+12}}{n+\frac54+\frac1{16n_0+12}}}\tag2 \end{align} Inequality $$(2)$$ implies that, for $$n\ge n_0$$, $$\boxed{\bbox[5pt]{\displaystyle\binom{2n}{n}\frac{\sqrt{n+\frac14+\frac1{16n_0+12}}}{4^n}\text{ is decreasing}}}\tag3$$

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 that for $$n\ge n_0\ge0$$, $$\boxed{\bbox[5pt]{\displaystyle\frac{4^n}{\sqrt{\pi\!\left(n+\frac14+\frac1{16n_0+12}\right)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi\!\left(n+\frac14\right)}}}}\tag9$$

If we set $$n_0=0$$ in $$(9)$$, we get that for $$n\ge0$$, $$\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)}}}}\tag{10}$$

The Cross-Multiplication

For $$(1)$$: $$\scriptsize\left(n^2+n+\frac14\right)\left(n+\frac54+\frac1{16n_0+12}\right)-\left(n^2+2n+1\right)\left(n+\frac14+\frac1{16n_0+12}\right)=-\frac{n-n_0}{16n_0+12}\tag{11a}$$ which gives $$(1)$$, for $$n\ge n_0$$: $$\frac{n^2+n+\frac14}{n^2+2n+1}\le\frac{n+\frac14+\frac1{16n_0+12}}{n+\frac54+\frac1{16n_0+12}}\tag{11b}$$ For $$(4)$$: $$\scriptsize\left(n^2+n+\frac14\right)\left(n+\frac54\right)-\left(n^2+2n+1\right)\left(n+\frac14\right)=\frac1{16}\tag{12a}$$ which gives $$(4)$$, $$\frac{n^2+n+\frac14}{n^2+2n+1}\ge\frac{n+\frac14}{n+\frac54}\tag{12b}$$

• @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.
– robjohn
Commented Sep 16, 2014 at 15:05
• For finite $n$, you can use $0<O(\frac 1 {n^2})<\frac 1{72n}$ in $(11)$ (per Wikipedia).
– A.S.
Commented Feb 23, 2016 at 17:36
• @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. Commented Mar 1, 2016 at 19:38
• @robjohn, I'd appreciate a reference to cite too. +1 Commented Dec 6, 2017 at 14:40
• @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.
– robjohn
Commented Dec 6, 2017 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.

• $\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)
– robjohn
Commented Sep 16, 2014 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}$.

• @ThomasAndrews Ahh yes thank you for pointing that out. Commented Mar 14, 2013 at 0:21

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

• And how did you get that formula? Commented Dec 30, 2021 at 7:04

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

• I have applied MathJax. Please make sure everything is as intended. MathJax makes things easier to read.
– robjohn
Commented Mar 31, 2016 at 9:38

Here is a better estimate of the quantity. I am not going to prove it. Since I know about it, hence I am sharing and will put the reference.

$$\frac{1}{2\sqrt{n}} \le {2n \choose n}2^{-2n} \le \frac{1}{\sqrt{2n}}$$ Refer to Page 590 This is the text book "Boolean functions Complexity" by Stasys Jukna.

• Beside the fact that link-only answers are discouraged because the links can go stale, the linked PDF provides no hint of how to prove this inequality either; it simply provides a list of many formulas and inequalities with no proof. In any case, this inequality is less precise than the inequality given in the question.
– robjohn
Commented Mar 1, 2021 at 7:24

Since $$\frac1{4^n}\binom{2n}n=\prod_{k=1}^n\frac{2k-1}{2k}:=a_n.$$ we need to prove: $$\frac1{\sqrt{4n}} Observe that for $$n=1$$ we have $$\frac1{\sqrt{4n}}=a_n=\frac1{\sqrt{3n+1}}.$$
Since $$a_{n}=a_{n-1}\cdot\frac{2n-1}{2n}$$ it suffices therefore to prove for $$n>1$$: $$\sqrt{\frac{4(n-1)}{4n}}<\frac{2n-1}{2n}<\sqrt{\frac{3(n-1)+1}{3n+1}}.$$ or $$\frac{n-1}{n}<\frac{(2n-1)^2}{(2n)^2}<\frac{3n-2}{3n+1}.$$ The left and right inequalities are equivalent to: $$(2n)^2(n-1)<(2n-1)^2n \iff 4n^3-4n^2<4n^3-4n^2+4n$$ and $$(2n-1)^2(3n+1)<(3n-2)(2n)^2 \iff 12n^3-8n^2-n+1<12n^3-8n^2,$$ respectively, both of which are trivial.