# Upper limit on the central binomial coefficient

What is the tightest upper bound we can establish on the central binomial coefficients $2n \choose n$ ?

I just tried to proceed a bit, like this:

$n! > n^{\frac{n}{2}}$

for all $n>2$. Thus,

$\binom{2n}{n} = \frac{ (n+1) \ldots (2n) }{n!} < \frac{\left(\frac{\sum_{k=1}^n (n+k) }{n}\right)^n }{n^{n/2}} = \frac{ \left( \frac{ n^2 + \frac{n(n+1)}{2} }{n} \right) ^n}{n^{n/2}} = \left( \frac{3n+1}{2\sqrt{n}} \right)^n$

But, I was searching for more tighter bounds using elementary mathematics only (not using Stirling's approximation etc.).

• The simplest upper bound to prove is $4^n$ (which is still stronger than your bound) and just follows from the binomial expansion of $(1+1)^{2n}$. Peter's answer gives a less wasteful estimate. Jun 14 '13 at 13:00
• I should have thought about it. Yes, Peter's bound is very good, I tested it too. Jun 14 '13 at 13:54

Here's a way to motivate and refine the argument that Péter Komjáth attributes to Erdős.

Start by computing the ratio between the $$n$$-th and $$(n-1)$$-st central binomial coefficients: $${2n \choose n} \left/ {2(n-1) \choose n-1} \right. = \frac{(2n)! \phantom. / \phantom. n!^2}{(2n-2)! \phantom. / \phantom. (n-1)^2} = \frac{(2n)(2n-1)}{n^2} = 4 \left( 1 - \frac1{2n} \right).$$ For large $$n$$, this ratio approaches $$4$$, suggesting that $$2n \choose n$$ grows roughly as $$4^n$$. If the factor $$1 - \frac1{2n}$$ were $$1 - \frac1n = (n-1)/n$$, the growth would be exactly proportional to $$n^{-1} 4^n$$. Since $$1 - \frac1{2n}$$ is (for large $$n$$) nearly the square root of $$1 - \frac1n$$, the actual asymptotic should be proportional to $$n^{-1/2} 4^n$$. So we introduce the ratio $$r_n := \left( {2n \choose n} \left/ \frac{4^n}{\sqrt n} \right. \right)^2 = \frac{n}{16^n} {2n \choose n}^2.$$ Then $$\frac{r_n}{r_{n-1}} = \left( 1 - \frac1{2n} \right)^2 \left/ \left( 1 - \frac1n \right) \right. = \frac{(2n-1)^2}{(2n-2)(2n)} \gt 1.$$ Thus $$r_{n-1} < r_n$$; and since $$r_1 = (2/4)^2 = 1/4$$ we have by induction $$r_1 \lt r_2 \lt r_3 \lt r_4 \lt \cdots \lt r_n = \frac12 \frac{1 \cdot 3}{2 \cdot 2} \frac{3 \cdot 5}{4 \cdot 4} \frac{5 \cdot 7}{6 \cdot 6} \cdots \frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} \frac{2n-1}{2n}.$$ Each $$r_{n_0}$$ gives a lower bound on $$r_n$$, and thus on $$2n\choose n$$, for all $$n \geq n_0$$. The OP asked for upper bounds, so consider $$R_n := \frac{2n}{2n-1} r_n = \frac{n}{\left(1-\frac 1{2n}\right)16^n} {2n \choose n}^2.$$ Now $$R_{n+1}/R_n = (2n-1)(2n+1) \phantom. / \phantom. (2n)^2 = (4n^2-1) \phantom. / \phantom. (4n^2) \lt 1$$, so $$\frac12 = R_1 \gt R_2 \gt R_3 \gt R_4 \gt \cdots \gt R_{n+1} = \frac12 \frac{1 \cdot 3}{2 \cdot 2} \frac{3 \cdot 5}{4 \cdot 4} \frac{5 \cdot 7}{6 \cdot 6} \cdots \frac{(2n-3)(2n-1)}{(2n-2)(2n-2)}.$$ It follows that $$R_n \geq r_{n'}$$ for any $$n,n'$$, so $$R_1=1/2$$, $$R_2=3/8$$, $$R_3=45/128$$, etc. are a series of upper bounds on every $$r_n$$. Since moreover $$r_n / R_n = 1 - \frac1{2n} \rightarrow 1$$ as $$n \rightarrow \infty$$, both $$r_n$$ and $$R_n$$ converge to a common limit that is an upper bound on every $$r_n$$. If we accept Wallis's product (which is classical though not as elementary as everything else in our analysis), then we can evaluate this common limit as $$1/\pi$$ and thus recover the asymptotically sharp upper bound $${2n \choose n} < 4^n / \sqrt{\pi n}$$.

• +1, and let me challenge your statement that the Wallis product is not as elementary, by pointing to the Monthly note math.chalmers.se/~wastlund/monthly.pdf and the 16th Christmas Tree Lecture by Don Knuth, "Why pi?" (now on youtube). Jul 1 '13 at 16:58
• Your answer has been cited in this paper that I was just reading, mentioning it here as a token of appreciation: arxiv.org/pdf/2005.10009.pdf
– NULL
Jul 28 '20 at 19:59

Even the asymptotically sharp inequality ${2n \choose n} < 4^n \left/ \sqrt{\pi n} \right.$ has a short proof: $${2n \choose n} = \frac{4^n}{\pi} \int_{-\pi/2}^{\pi/2} \cos^{2n} x \phantom. dx < \frac{4^n}{\pi} \int_{-\pi/2}^{\pi/2} e^{-nx^2} dx < \frac{4^n}{\pi} \int_{-\infty}^{\infty} e^{-nx^2} dx = \frac{4^n}{\sqrt{\pi n}}.$$ In the first step, the formula for $\int_{-\pi/2}^{\pi/2} \cos^{2n} x \phantom. dx$ can be proved by induction via integration by parts, or using the Beta function.

The third step is clear, and the last step is the well-known Gaussian integral. So we need only justify the the second step.

There we need the inequality $\cos x \leq e^{-x^2/2}$, or equivalently $$\log \cos x + \frac{x^2}{2} \leq 0,$$ for $\left|x\right| < \pi/2$, with equality only at $x=0$. This is true because $\log \cos x +\frac12 x^2$ is an even function of $x$ that vanishes at $x=0$ and whose second derivative $-\tan^2 x$ is negative for all nonzero $x \in (-\pi/2, \pi/2)$. QED

• I'm not sure what counts as elementary in this game, but I would think the easiest proof that $\frac{1}{\pi} \int \cos^{2n} x dx = \binom{2n}{n}/4^n$ is to write $\cos x = (e^{ix} + e^{-ix})/2$ and expand $\cos^{2n}$ by the binomial theorem. Jul 1 '13 at 14:18

Erdos remarked somewhere the bound
$${{2n}\choose{n}}<\frac{4^n}{\sqrt{2n+1}}.$$ This can be established by induction: $${{2n+2}\choose{n+1}}=\frac{(2n+1)(2n+2)}{(n+1)(n+1)}{{2n}\choose{n}}$$ and if we have the bound for $n$, we only have to show $$\frac{2(2n+1)}{(n+1)\sqrt{2n+1}}<\frac{4}{\sqrt{2n+3}}$$ which reduces to $4n^2+8n+3<4n^2+8n+4$.

• This bound is pretty close to optimal because (unless I've computed badly) Stirling's approximation gives $4^n/\sqrt{\pi n}$. Jun 14 '13 at 13:26

Noam Elkies notes that there is a quick proof of $$\binom{2n}{n} \leq \frac{4^n}{\sqrt{\pi n}}$$ by writing $$\binom{2n}{n} = \frac{4^n}{\pi} \int_{-\pi/2}^{\pi/2} \cos^{2n} x dx$$ and bounding $\cos^2 x \leq e^{-x^2}$.

There is an equally good lower bound by a similar method: $$\int_{-\pi/2}^{\pi/2} \cos^{2n} x dx =\int_{-\pi/2}^{\pi/2} \frac{\sec^2 x dx}{(\tan^2 x+1)^{n+1}} = \int_{- \infty}^{\infty} \frac{du}{(1+u^2)^{n+1}} \geq \int_{- \infty}^{\infty} e^{-(n+1) u^2} du$$ so $$\binom{2n}{n} \geq \frac{4^n}{\sqrt{\pi (n+1)}}.$$ Here the inequality $\tfrac{1}{1+u^2} \geq e^{-u^2}$ follows from the standard bound $e^y \geq 1+y$ for $y\geq 0$.

We may prove without using integrals that $$\frac1{\sqrt{\pi n}}\geqslant 4^{-n}{2n\choose n}\geqslant \frac{1}{\sqrt{\pi(n+1/2)}}.\quad\quad (1)$$ (1) is equivalent to $$2n\left(4^{-n}{2n\choose n}\right)^2=\frac12\prod_{k=2}^n \frac{(2k-1)^2}{2k(2k-2)}:=d_n\leqslant \frac2\pi\leqslant c_n\\:=(2n+1)\left(4^{-n}{2n\choose n}\right)^2=\prod_{k=1}^n\left(1-\frac1{4k^2}\right)$$ (the identities are straightforward by induction).

Denote $$m:=2n+1$$. It is not hard to show that $$\sin mx=p_m(\sin x)$$ for a polynomial of degree $$m$$ in $$\sin x$$. The roots of $$p_m$$ are $$\sin \frac{k\pi}{2n+1}$$ for $$k=-n,\ldots,n$$. Thus $$\sin (2n+1)x=(2n+1)\sin x\prod_{k=1}^n\left(1-\frac{\sin^2 x}{\sin^2 \frac{k\pi}{2n+1}}\right)$$ (the multiple $$2n+1$$ comes from dividing by $$x$$ and putting $$x=0$$). Put $$x=\frac{\pi}{4n+2}$$. Using the inequality $$\sin tx\leqslant t\sin x$$ (which may be proved, for example, by induction in $$t=1,2,\ldots$$ from the identity $$\sin(t+1)x=\sin tx\cos x+\sin x\cos tx$$) for $$t=2k$$ ($$k=1,2,\ldots,n$$) we get $$1\leqslant (2n+1)\sin\frac{\pi}{4n+2}\prod_{k=1}^n\left(1-\frac1{4k^2}\right)\leqslant \frac{\pi}{2}c_n,\quad c_n\geqslant \frac{2}\pi.$$ Analogously we get $$\cos 2nx=\prod_{k=1}^n\left(1-\frac{\sin^2 x}{\sin^2 \frac{\pi(2k-1)}{4n}}\right).$$

Dividing by $$1-\frac{\sin^2 x}{\sin^2 \frac{\pi}{4n}}$$ and substituting $$x=\frac{\pi}{4n}$$ (for computing the LHS at this point use l'Hôpital rule) we get $$n\tan\frac{\pi}{4n}\leqslant \prod_{k=2}^n\left(1-\frac1{(2k-1)^2}\right)=\frac1{2d_n},\quad d_n\leqslant \frac1{2n\tan \frac{\pi}{4n}}\leqslant \frac2\pi.$$

UPD. This is less or more equivalent to Yaglom brothers proof (1953), see their Russian paper (it contains also the derivation of identities $$\sum 1/n^2=\pi^2/6$$ and $$\sum (-1)^{k-1}/(2k-1)=\pi/4$$ using these trigonometric things.)

• Nice proof! Is there an easy way to get the tight lower bound $1/\sqrt{\pi n+1}$? It has such a nice form..
– aorq
Jan 1 at 2:54
• @aorq It is not so much tight. The sequence $4^{-n}{2n\choose n}\sqrt{n+c}$ eventually decreases if $c>1/4$ (this is straightforward: divide the squares of two consecutive terms and subtract 1) and its limit equals $1/\sqrt{\pi}$. Thus for large enough $n$ we get the upper bound $1/\sqrt{\pi (n+c)}$. For $c=1/\pi$ this just works from the very beginning. Jan 1 at 9:51
• Yes, I know that it's tight in the weakest possible sense, namely equality for $n=0$ and poor otherwise. Shortly after I wrote my comment, I saw that $1/\sqrt{\pi(n+1/4)}$ was tighter in a more meaningful sense (on the other side), namely ever better as $n\to\infty$. Thanks for your explanation!
– aorq
Jan 1 at 14:41
• Warning: $1/\sqrt{\pi(n+1/4)}$ is an upper bound Jan 1 at 15:08

You may also prove $${2n\choose n}\sim \frac{4^n}{\sqrt{\pi n}}$$ using the combinatorial meaning of $${2n\choose n}$$ and the area-of-a-circle definition of $$\pi$$. That is probably the most elementary we can hope for.

First of all, if $$a_n:=\sqrt{n+1/4}{2n\choose n}4^{-n}$$ and $$b_n:=\sqrt{n+1/2}{2n\choose n}4^{-n}$$, we may check that $$a_n\leqslant b_n$$, $$a_n$$ increases and $$b_n$$ decreases, thus $$a_n$$, $$b_n$$ have a common positive finite limit which we denote $$\alpha$$, and $$a_n\leqslant \alpha\leqslant b_n$$. Since $$b_n/a_n=1+O(1/n)$$, we get $$a_n=\alpha+O(1/n)$$, and also $$c_n=\alpha+O(1/n)$$ where $$c_n:=\sqrt{n}{2n\choose n}4^{-n}$$.

We should prove that $$\alpha=1/\sqrt{\pi}$$.

Use the combinatorial identity $$4^{-n}\sum_{k=0}^n k{2k\choose k}(n-k){2(n-k)\choose n-k}=\frac{n(n-1)}8.\quad (\heartsuit)$$ LHS of $$(\heartsuit)$$ equals $$\sum_{k=0}^n \sqrt{k(n-k)}c_kc_{n-k}=\sum_{k=0}^n \sqrt{k(n-k)}\left(\alpha^2+O\left(\frac1k+\frac1{n-k}\right)\right)\\=\alpha^2\sum_{k=0}^n\sqrt{k(n-k)}+O\left(n\sum_{k=0}^n\frac1{\sqrt{k(n-k)}}\right)=\alpha^2\cdot \frac{\pi n^2}8+o(n^2),$$ since the union of rectangles $$[k,k+1]\times [0,\sqrt{k(n-k)}]$$ approximates the upper semi-circle with the horizontal diameter $$[0,n]$$.

Thus $$\alpha^2\pi/8=1/8$$ and $$\alpha=1/\sqrt{\pi}$$.

You could use instead of $$(\heartsuit)$$ the more famous identity $$4^{-n}\sum_{k=0}^n {2k\choose k}{2(n-k)\choose n-k}=1$$ this gives $$\alpha^2\int_0^1\frac{dx}{\sqrt{x(1-x)}}=1$$ (the integral equals $$\pi$$ of course, but this is less "elementary" then the area of a circle.)

This argument is similar to J. Wästlund's (An elementary proof of Wallis' product formula for $$\pi$$, 2007).

Since it gives tighter bounds, I will reproduce my answer from MathSE.

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