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

  • 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.2012-12-22
  • 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?2012-12-22
  • 0
    @anonymous $2n+1 \leq (1+n)^2$ ?2012-12-22
  • 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$.2012-12-23
  • 0
    [Related](http://math.stackexchange.com/q/439026/462).2013-07-09

4 Answers 4

9

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

  • 0
    Nameless, $2n+1 \leq 2^n$ because $2n+1 \leq n^2$ ?2012-12-22
  • 0
    @doniyor Hint: (it takes another induction)2012-12-22
  • 0
    @doniyor To prove $2n+1\le 2^n$ you will need another, but much simpler, induction2012-12-22
  • 0
    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?2012-12-23
  • 0
    @doniyor I think my edit will clear your doubts2012-12-23
  • 0
    oh okay, thanks, so in cases like this, do i have to prove any inequality on the way of main proof?2012-12-23
  • 0
    @doniyor Perhaps you will need many inductions to reach the end. It all depends on what the problem is2012-12-23
  • 0
    yeah you are right..2012-12-23
3

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

2

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

0

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