Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

3 Answers

up vote 7 down vote accepted

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

share|improve this answer
1  
+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
add comment

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

share|improve this answer
2  
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
add comment

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

share|improve this answer
    
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
2  
[Typo: $84$ should be $8n$.] –  Noam D. Elkies Jun 14 '13 at 14:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.