2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Stirling approximation. $\endgroup$ – Ahmad Oct 9 '18 at 10:06
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Oct 9 '18 at 17:53
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – jacky Feb 9 at 8:03
0
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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