How to prove the following inequality $\sqrt n {2n\choose n}<2^{2n-\frac{1}{2}} \,n\in \mathbb{N}$?

Question

How to prove the following inequality?

$$\sqrt n {2n\choose n}<2^{2n-\frac{1}{2}} \quad n\in \mathbb{N}$$

I tried to prove it by using mathematical induction, but I still get contradiction

Answer 1

The inequality is false for $n=4$. Left: $2\cdot\binom{2n}{n}=140$, and right: $2^8/2=128$.

That sentence is wrong because I misread the statement.

The orignal inequality can be written as $$ \binom{2n}{n} < \frac{4^n}{\sqrt{2n}} $$ This holds at $n=1$ (as $2<4/\sqrt2$) but the obvious inductive step hits a snag.

The somewhat stronger inequality $$ \binom{2n}{n}\le \frac{4^n}{\sqrt{3n+1}} $$ is an equality for $n=1$ (for $2=4/\sqrt4$) but it can be proven inductively and the inductive step will show that it becomes strict from $n=2$.

Answer 2

$$\frac{1}{4^n}\binom{2n}{n}=\frac{(2n)!}{(2^n n!)^2}=\frac{(2n-1)!!}{(2n)!!}=\prod_{k=1}^{n}\left(1-\frac{1}{2k}\right) $$ and by squaring both sides $$ \left[\frac{1}{4^n}\binom{2n}{n}\right]^2 = \prod_{k=1}^{n}\left(1-\frac{1}{k}+\frac{1}{4k^2}\right)=\frac{1}{4}\prod_{k=2}^{n}\left(1-\frac{1}{k}\right)\prod_{k=2}^{n}\left(1+\frac{1}{4k(k-1)}\right) $$ where the first product in the RHS is telescopic.
By using $1+x\leq e^x$ and a telescopic sum we get: $$ \left[\frac{1}{4^n}\binom{2n}{n}\right]^2 \leq \frac{1}{4n} \exp\sum_{k=2}^{n}\frac{1}{4k(k-1)}=\frac{1}{4n}\exp\frac{n-1}{4n}\leq \frac{e^{1/4}}{4n} $$ then $$ \frac{1}{4^n}\binom{2n}{n}\leq \frac{e^{1/8}}{2\sqrt{n}}\qquad\Longrightarrow\qquad \boxed{\sqrt{n}\binom{2n}{n}\leq 2^{2n\color{red}{-\frac{4}{5}}}.} $$

---

Alternative approach: $\tan(x)\geq x$ leads to $\cos(x)\leq e^{-x^2/2}$ over $(0,\pi/2)$, by integration and exponentiation. On the other hand integration by parts gives $$ \frac{1}{4^n}\binom{2n}{n}=\frac{2}{\pi}\int_{0}^{\pi/2}\left(\cos\theta\right)^{2n}\,d\theta $$ hence $$ \frac{1}{4^n}\binom{2n}{n} \leq \frac{2}{\pi}\int_{0}^{\pi/2} e^{-nx^2}\,dx < \frac{2}{\pi}\int_{0}^{+\infty}e^{-nx^2}\,dx = \frac{1}{\sqrt{\pi n}}$$ and $$ \boxed{\sqrt{n}\binom{2n}{n}\leq 2^{2n\color{red}{-\frac{\log\pi}{\log 4}}}.} $$ This is actually the optimal constant we may insert in such place.

Answer 3

We have that

$$\sqrt n {2n\choose n}<2^{2n-\frac{1}{2}}\iff \frac{\sqrt {2n}(2n)!}{4^n(n!)^2}<1$$

and by Stirling's bound

$$\sqrt{2\pi}\ n^{n+\frac12}e^{-n} \le n! \le e\ n^{n+\frac12}e^{-n}$$

we have

$$\frac{\sqrt {2n}(2n)!}{4^n(n!)^2}\le \frac{\sqrt {2n}e (2n)^{2n+\frac12}e^{-2n}} {4^n(\sqrt{2\pi}\ n^{n+\frac12}e^{-n})^2}= \frac{2n\, 4^nn^{2n}e^{-2n+1}} {4^n \,2\pi\, n^{2n+1}e^{-2n}}= \frac{ e^{}} { \pi\, }<1$$

Answer 4

We have $$\begin{align}{2(n+1)\choose n+1}&=2\cdot{2n+1\choose n}\\ &=2{2n\choose n}+2{2n\choose n-1}\\&=2{2n\choose n}\cdot\left(1+\frac{n}{n+1}\right)\\&={2n\choose n}\cdot \frac{4n+2}{n+1}, \end{align}$$ hence if we let $a_n=\frac{\sqrt n{2n\choose n}}{2^{2n-\frac12}}$, we have $$ \begin{align}\frac{a_{n+1}}{a_n}&=\frac{\sqrt{n+1}{2(n+1)\choose n+1}2^{2n-\frac12}}{2^{2n+2-\frac12}\sqrt{n}{2n\choose n}}\\ &=\frac{(4n+2)\sqrt{n+1}}{(4n+4)\sqrt n}\\ &=\sqrt{\frac{(2n+1)^2(n+1)}{4(n+1)^2n}}\\ &=\sqrt{\frac{(2n+1)^2}{4(n+1)n}}\\ &=\sqrt{1+\frac{1}{4n(n+1)}}\end{align}$$ which is unfortunately slightly greater than $1$, and therefore a straightforward proof by induction fails.

But we find by telescoping and the arithmetic-geometric inequality $$\begin{align}\sqrt[n]{\frac{a_{n+1}^2}{a_1^2}}&=\sqrt[n]{\frac{a_{n+1}^2}{a_n^2}\frac{a_{n}^2}{a_{n-1}^2}\cdots \frac{a_2^2}{a_1^2}}\\ &=\sqrt[n]{\left(1+\frac1{4n(n+1)}\right)\left(1+\frac1{4(n-1)n}\right)\cdots \left(1+\frac1{4\cdot 1\cdot 2}\right)} \\ &\le \frac1n\left(1+\frac1{4n(n+1)}+1+\frac1{4(n-1)n}+\ldots +1+\frac1{4\cdot 1\cdot 2}\right)\\ &=1+\frac1{4n}\left(\frac1{n(n+1)}+\frac1{(n-1)n}+\ldots +\frac1{1\cdot 2}\right)\\ &=1+\frac1{4n}\left(\frac1n-\frac1{n+1}+\frac1{n-1}-\frac1n+\ldots+\frac11-\frac12\right)\\ &=1+\frac{1-\frac1{n+1}}{4n}\\ &=1+\frac1{4(n+1)} \end{align}$$ and therefore $$ \frac{a_n}{a_1}\le \left(1+\frac1{4(n+1)}\right)^n<\sqrt[4]{\left(1+\frac1{4(n+1)}\right)^{4(n+1)}}.$$ When introducing $e$, one commonly shows that the sequence $\left(1+\frac1k\right)^k$ is strictly increasing with limit $e(<4)$. Therefore $$ a_n<a_1\sqrt[4]e=\frac{\sqrt[4]e}{\sqrt 2}=\sqrt[4]{\frac e4}<1,$$ as was to be shown.