$2^{\sqrt{n}}>n^2$ inequality proof

Question

I am trying to do some trick with lim but get stuck on $2^{\sqrt{n}}>n^2$. I want to prove it for n large enough but don't know how to do induction step. Maybe this fact does not require a proof at all...

Answer 1

First replace $n$ by $m^2$ to get rid of the square root and study

$$2^m>m^4.$$

When you increment $m$, you multiply the LHS by the constant $2$, and the RHS by the factor $$\left(1+\frac1m\right)^4.$$

We have $2^{16}=16^4$ and for $m>16$,

$$\left(1+\frac1m\right)^4<1.3<2$$ which proves the claim true for $n>256$.

Answer 2

Taking logarithms we have $$2^{\sqrt{n}}>n^2\Leftrightarrow \sqrt{n}\log 2>2\log n.$$ Now consider the function $f(x)=\frac{2\log x}{\sqrt{x}\log 2}$ and apply L'Hopital's rule to obtain $$ \lim_{x\to\infty}f(x)\overset{L'H}{=}\lim_{x\to\infty}\frac{2/x}{\frac{\log2}{2\sqrt{x}}}=\frac{4}{\log2}\lim_{x\to\infty}\frac{1}{\sqrt{x}}=0. $$

Answer 3

Hint

put $\sqrt{n}=x$ and try to prove that

$2^x>x^4$ by studying the function

$$f\;:\;x\mapsto x\ln(2)-4\ln(x)$$ at$ [1,+\infty)$.

$$f'(x)=\ln(2)-\frac{4}{x}$$

it increases from $x=\frac{4}{\ln(2)}$ and becomes positive for large enough $x$, since it goes to $+\infty$ when $x\to +\infty$.

Answer 4

Taking for example $n=400$ as a base case $$2^\sqrt{400}=2^{20}>10^6>400^2=16\cdot 10^4,x=\sqrt{n}\\2^x>x^4\\2^{x+1}>(x+1)^4\\2\cdot 2^x>x^4+4x^3+6x^2+4x+1\\x^4+15x^3>x^4+4x^3+6x^2+4x+1\\2^x+15x^3>x^4+15x^3\\\frac{3}{4}x^4\geq15 x^3\\2\cdot2^x>2^x+\frac{3}{4}2^x>x^4+4x^3+6x^2+4x+1$$ The $\frac{3}{4}x^4\geq15 x^3$ comes since $x\geq 20$

Answer 5

Expressing $2^{\sqrt{n}}=e^{\sqrt{n}\log2}$ in power series we find that \begin{align} e^{\sqrt{n}\log2}=&1+\sqrt{n}\log2+\frac{n\log^22}{2!}+\frac{n\sqrt{n}\log^32}{3!}+\frac{n^2\log^42}{4!}+\frac{n^2\sqrt{n}\log^52}{5!}+\cdots\\ >&n^2\sqrt{n}\,\frac{\log^52}{5!}. \end{align} So for $n\geq\left(\frac{5!}{\log^52}\right)^2$ we have $$ 2^\sqrt{n}>n^2\underbrace{\sqrt{n}\,\frac{\log^52}{5!}}_{\geq1}\geq n^2. $$

Answer 6

An easy induction argument establishes the inequality $2^k\ge4k+4$ for $k\ge5$: the base case is $2^5=32\ge24=4\cdot5+4$, and the inductive step is

$$2^{k+1}=2\cdot2^k\ge2(4k+4)\ge4k+8=4(k+1)+4$$

Now every positive integer $n$ lies between two consecutive even powers of $2$: for some $k$, $2^{2k+2}\gt n\ge2^{2k}$. Thus, if $n\ge2^{2\cdot5}=1024$, we have

$$2^\sqrt n\ge2^{\sqrt{2^{2k}}}=2^{2^k}\ge2^{4k+4}=(2^{2k+2})^2\gt n^2$$

Remark: I tried to get this argument to kick in at the "correct" starting point, $n=2^8=256$ (i.e., $k=4$), but couldn't make it work. If anyone sees a way to do it, please comment!