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

$\endgroup$
5
  • 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$ Dec 22, 2012 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$ Dec 22, 2012 at 19:20
  • $\begingroup$ @anonymous $2n+1 \leq (1+n)^2$ ? $\endgroup$
    – doniyor
    Dec 22, 2012 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$ Dec 23, 2012 at 21:20
  • $\begingroup$ Related. $\endgroup$ Jul 9, 2013 at 4:39

4 Answers 4

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

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

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

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

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