# Prove central binomial coefficient upper bound

I am trying to prove that $$\binom{2n}{n} < \frac{4^n}{\sqrt{2n}}$$. I tried induction, but with no effect (all I can get to is $$(2n+1)(2n+2) < 4\sqrt{n(n+1)}$$ which is false)

• Stirling approximation. – Ahmad Oct 9 '18 at 10:06
• @Ahmad: of course, but the usual way is to use bounds for $\frac{1}{4^n}\binom{2n}{n}$ to prove Stirling's approximation/double inequality. – Jack D'Aurizio Oct 9 '18 at 17:53

We have $$\frac{1}{4^n}\binom{2n}{n} = \frac{2}{\pi}\int_{0}^{\pi/2}\cos^{2n}\theta\tag{1}$$ by integration by parts. Since $$\tan\theta>\theta$$ over $$(0,\pi/2)$$ we have $$\cos\theta \leq e^{-\theta^2/2}$$, hence $$\frac{1}{4^n}\binom{2n}{n}\leq \frac{2}{\pi}\int_{0}^{\pi/2} e^{-n\theta^2}\,d\theta < \frac{2}{\pi}\int_{0}^{+\infty} e^{-n\theta^2}\,d\theta = \frac{1}{\sqrt{\pi n}}.\tag{2}$$

• thanku Jack $\displaystyle f(x)=\cos(x)\cdot e^{\frac{x^2}{2}}=e^{\frac{x^2}{2}}(x\cos x-\sin x)=e^{\frac{x^2}{2}}\cos x(x-\tan x)<0.$ so $f(x)<f(0)\implies \cos (x)<e^{-\frac{x^2}{2}}$ for $x\in \bigg(0,\frac{\pi}{2}\bigg)$ – jacky Feb 9 at 8:03

$$n^n e^{-n}\sqrt{2\pi n} < n! < n^n e^{-n} \sqrt{2\pi n} (1+\frac{1}{8n})$$ this is Stirling approximation

So $$\binom{2n}{n} \leq \frac{(2n)^{2n} e^{-2n} \sqrt{4\pi n} (1+\frac{1}{16n})}{(n^n e^{-n} \sqrt{2\pi n})^2} = \frac{4^n (n)^{2n} e^{-2n} \sqrt{4\pi n} (1+\frac{1}{16n})}{n^{2n} e^{-2n}* 2\pi n} = \frac{4^n (1+\frac{1}{16n})}{\sqrt{\pi n}} \leq \frac{4^n}{\sqrt{2n}}$$.

• I think $n!<\sqrt{2\pi n}n^ne^{-n}\left(1+\frac{1}{12n}\right)$ is stronger. – Michael Rozenberg Oct 9 '18 at 12:29
• @MichaelRozenberg its actually $e^(\frac{1}{12n})$ which is slightly bigger than $\frac{1}{12n}$ buy anyway this part does not effect the proof. – Ahmad Oct 9 '18 at 18:34

Straight induction would be $${{2n+2}\choose{n+1}} =\frac{(2n+1)(2n+2)}{(n+1)(n+1)}{{2n}\choose{n}} <\frac{2(2n+1)}{n+1} \frac{4^n}{\sqrt{2n}}$$ So, we only have to prove that $$\frac{2(2n+1)}{n+1} \frac{1}{\sqrt{2n}} < \frac{4}{\sqrt{2n+2}}$$ which unfortunately is never true.

Fortunately, straight induction works for a slightly stronger claim: $${{2n}\choose{n}}<\frac{4^n}{\sqrt{2n+1}}$$ Indeed, $${{2n+2}\choose{n+1}}=\frac{(2n+1)(2n+2)}{(n+1)(n+1)}{{2n}\choose{n}} <\frac{2(2n+1)}{n+1}\frac{4^n}{\sqrt{2n+1}}$$ So, we only have to prove that $$\frac{2(2n+1)}{(n+1)\sqrt{2n+1}}<\frac{4}{\sqrt{2n+3}}$$ which is true for all $$n\ge0$$.