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

  • $\begingroup$ 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. $\endgroup$ – Johan Andersson Jun 14 '13 at 13:00
  • $\begingroup$ I should have thought about it. Yes, Peter's bound is very good, I tested it too. $\endgroup$ – 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
    $\begingroup$ +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). $\endgroup$ – 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

  • 3
    $\begingroup$ 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. $\endgroup$ – David E 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$.

  • $\begingroup$ This bound is pretty close to optimal because (unless I've computed badly) Stirling's approximation gives $4^n/\sqrt{\pi n}$. $\endgroup$ – Andreas Blass 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$.


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.