# 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. –  Johan Andersson Jun 14 '13 at 13:00
I should have thought about it. Yes, Peter's bound is very good, I tested it too. –  Mriganka Basu Roy Chowdhury 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)} \lt 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-\frac12}{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). –  Johan Wästlund Jul 1 '13 at 16:58

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. –  David Speyer 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}$. –  Andreas Blass Jun 14 '13 at 13:26
[Typo: $84$ should be $8n$.] –  Noam D. Elkies Jun 14 '13 at 14:47