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)
 A: 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}$$
A: 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$.
A: $ 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}}$.
