2

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)

user128409235
  • 643

3 Answers3

6

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

Jack D'Aurizio
  • 353,855
  • 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 09 '19 at 08:03
1

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

lhf
  • 216,483
0

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

Ahmad
  • 1,380
  • 1
  • 18
  • 37