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

-
Because it is false for $n = 3$, you should only expect the induction step to work when $n \ge 4$. I would call the case $n=4$ the base case, and check $n=0,1,2$ separately. –  Trevor Wilson Dec 22 '12 at 19:17
You know you can make $n^2 \leq 2^n$ by the induction assumption (once you've done Trevor's suggestion). Can you make $2n+1$ less than or equal to something useful? –  kigen Dec 22 '12 at 19:20
@anonymous $2n+1 \leq (1+n)^2$ ? –  doniyor Dec 22 '12 at 19:24
A proof that is not by induction: You check the cases $0,1,2,4$ directly. For $n\ge5$, note that $n^2=\binom{n}{1}+\binom{n}2+\binom{n}{n-2}<\sum_{i=0}^n\binom{n}{i}=2^n$. –  Andres Caicedo Dec 23 '12 at 21:20
–  Andres Caicedo Jul 9 '13 at 4:39

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

-
Nameless, $2n+1 \leq 2^n$ because $2n+1 \leq n^2$ ? –  doniyor Dec 22 '12 at 19:29
@doniyor Hint: (it takes another induction) –  Nameless Dec 22 '12 at 19:30
@doniyor To prove $2n+1\le 2^n$ you will need another, but much simpler, induction –  Nameless Dec 22 '12 at 19:32
sorry, i am coming back to your question again: i am trying to find why $2n+1\leq 2^n$ this is an induction proof for $n\geq3$, should i do it? –  doniyor Dec 23 '12 at 20:17
@doniyor I think my edit will clear your doubts –  Nameless Dec 23 '12 at 20:22

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

-

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

-

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

-