1

Question: For which values of n, $n^2 \leq 2^n$ holds? Prove it by simple induction.

This is what I have done so far:

We know that all natural numbers other than 3 works. So I will make the claim that $\forall n \in \mathbb{N}, n \neq 3: n^2 \leq 2^n$

Now to prove this:

Proof method: Simple induction

Let P(n) be that $\forall n \in \mathbb{N}, n \neq 3: n^2 \leq 2^n$.

Basic Step:

$5^2 = 25 \leq 2^5 = 32$

Then P(5) is true, because $5^2 \leq 2^5$

Inductive Step:

Assume $\forall k \in \mathbb{N}, k \neq 3: k^2 \leq 2^k$

Want to show that $P(k) \implies P(k+1)$

So, $k^2 \leq 2^k$

$2k^2 \leq 2(2^k)$

$2k^2 \leq 2^{k+1}$

$k^2 + k^2 \leq 2^{k+1}$

This is where I got stuck, trying to change the left hand side to $(k+1)^2$, I've tried working with the idea that $(k+1)^2 = k^2 + 2k + 1$, but wasn't able to really get anything out of it.

Any help will really be appreciated.

Hanul Jeon
  • 27,376
Mat
  • 131

2 Answers2

2

For your base case, I recommend you show that $n^2 \le 2^n$ works for $n=1$, $n=2$, and $n=4$ as well. If you show $n=4$, showing $n=5$ is unnecessary (since your induction step will take care of that).

About your inductive step, you ended with:

$$2k^2 \le 2^{k+1}$$

You now need to show $(k+1)^2 \le 2k^2$, which implies that $(k+1)^2 \le 2^{k+1}$, which is what you want to show. Then we see that:

$$4 \le k$$ $$1+\sqrt{2} \le k$$ $$2 \le (k-1)^2$$ $$2k+1 \le k^2$$ $$k^2+2k+1 \le 2k^2$$ $$(k+1)^2 \le 2k^2$$ $$(k+1)^2 \le 2^{k+1}$$

user2825632
  • 2,881
1

We assume $k^2<2^k$ for some value of $k$. From there:

$(k+1)^2<2^{k+1}$

$k^2+2k+1<2*2^k$

$k^2+2k+1<2^k+2^k$

$k^2<2^k$ by our assumption, so we are now left with:

$2k+1<2^k$

$2k+1<k^2\implies2k+1<k^2<2^k\implies2k+1<2^k$

From basic algebra, if $a<b$ and $c<d$, then $a+c<b+d$.

Letting $a=2k+1$, $b=d=2^k$, and $c=k^2$ should prove the theorem. Q.E.D.

AlgorithmsX
  • 4,560