Proof of $n^2 \leq 2^n$.

Question

I am trying to prove that $n^2 \leq 2^n$ for all natural $n$ with $n \ne 3$.
My steps are:

• induction base case: $n=0:$ $0² \leq 2⁰$ which is okay.
• inductive step: $n \rightarrow n+1:$ $(n+1)²\leq2^{n+1}$ $$(n+1)^2 = n^2 + 2n + 1 = ...help...\leq 2^{n+1}$$

I know the bernoulli inequality but don't know where to use it, if I even need to. I have problems when it comes to proving things which are based on orders..

Answer 1

First since one must have $n\neq 3$, the induction base must be $n=4$. For the induction step: Suppose $n^2\le 2^n$. Then, $$(n+1)^2=n^2+2n+1\le 2^n+2n+1\le 2^n+2^n=2^{n+1}$$ because $2n+1\le 2^n$ for $n\ge 3$ (why is this true?).

If you had started with inductive base $0,1$ or $2$, then you would have ran into problems because $2n+1\le 2^n$ doesn't hold for $n=2$

Proof of $2n+1\le 2^n$ for $n\ge 3$.

Induction base: For n=3, $$2\cdot 3+1=7\le 8=2^3$$ Induction step: Assume that for $n\ge 3$, $2n+1\le 2^n$. Then $$2(n+1)+1=2n+1+2\le 2^n+2\le 2^n+2^n=2^{n+1}$$ and so we are done

Answer 2

An analysis type proof.

$x^{1/x}$ has its maximum at $x = e$ and is increasing for $1 < x < e$ and decreasing for $x > e$.

$2^{1/2} = 4^{1/4}$, so $x^{1/x} < 2^{1/2}$ for $x > 4$ or $x^2 < 2^x$ for $x > 4$.

I am surprised that this worked out so nicely.

Obvious generalization: If $x > e$ and $y$ satisfies $1 < y < e$ and $y^{1/y} = x^{1/x}$ then $z^{1/z} < y^{1/y}$ for $z > x$ or $z^y < y^z$ for $z > x$.

Answer 3

Another possibility is to write $$2^n = \sum\limits_{k=0}^n C_n^k \geq 1+n+ \frac{n(n-1)}{2} + \frac{n(n-1)(n-2)}{6} \geq n^2$$ for $n \geq 5$. It can be interpreted as follow: the set $\{1,...,n\}$ has at least $n^2$ subsets of cardinality at most three, and exactly $2^n$ subsets; therefore, $2^n \geq n^2$.

Answer 4

Here's another analytic proof. First note that $$\frac{2}{\operatorname{log}{2}}\operatorname{log}{4}=4.$$ The value of $2/\operatorname{log}{2}$ is a bit less than $3$. (Proof. $\frac{2}{\operatorname{log}2}<3\Leftrightarrow 2<3\operatorname{log}2\Leftrightarrow e^2<e^{3\operatorname{log}2}=8$, which is clearly true as $e<2.75=\frac{11}{4}$. $\square$) Thus for $n>4$, $$\frac{d}{dn}\left(\frac {2} {\operatorname{log} {2}}\operatorname{log} {n}\right) = \frac {2} {\operatorname{log}{2}}\frac{1}{n} <1=\frac{d}{dn}\left(n\right).$$ Thus $\frac{2}{\operatorname{log}{2}}\operatorname{log}{n}\leq n$ for $n\geq 4$ by the racetrack principle. Equivalently, $\log_2 n^2 \leq \log_2 2^n$, from which we obtain $n^2\leq 2^n$.