Prove central binomial coefficient upper bound

Question

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)

Answer 1

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

Answer 2

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

Answer 3

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