Proof of $n^2 \leq 2^n$. 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.. 
 A: 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
A: 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$.
A: 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$.
A: 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$.
