Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
1  
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? –  neuguy Dec 22 '12 at 19:20
    
@anonymous $2n+1 \leq (1+n)^2$ ? –  doniyor Dec 22 '12 at 19:24
1  
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
    
Related. –  Andres Caicedo Jul 9 '13 at 4:39

4 Answers 4

up vote 8 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.