5
$\begingroup$

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

Improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Trevor Wilson Dec 22 '12 at 19:17
  • 1
    $\begingroup$ 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? $\endgroup$ – Gyu Eun Lee Dec 22 '12 at 19:20
  • $\begingroup$ @anonymous $2n+1 \leq (1+n)^2$ ? $\endgroup$ – doniyor Dec 22 '12 at 19:24
  • 1
    $\begingroup$ 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$. $\endgroup$ – Andrés E. Caicedo Dec 23 '12 at 21:20
  • $\begingroup$ Related. $\endgroup$ – Andrés E. Caicedo Jul 9 '13 at 4:39
9
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Nameless, $2n+1 \leq 2^n$ because $2n+1 \leq n^2$ ? $\endgroup$ – doniyor Dec 22 '12 at 19:29
  • $\begingroup$ @doniyor Hint: (it takes another induction) $\endgroup$ – Nameless Dec 22 '12 at 19:30
  • $\begingroup$ @doniyor To prove $2n+1\le 2^n$ you will need another, but much simpler, induction $\endgroup$ – Nameless Dec 22 '12 at 19:32
  • $\begingroup$ 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? $\endgroup$ – doniyor Dec 23 '12 at 20:17
  • $\begingroup$ @doniyor I think my edit will clear your doubts $\endgroup$ – Nameless Dec 23 '12 at 20:22
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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