Show that $2^n > n^2$ whenever n>4.

Question

Let $S(n)$ be the proposition "$2^n > n^2$"

Basis step: $S(5)$ is true, since $2^5 = 32$, $ 32 > 25 = 5^ 2$

Inductive step:

Induction hypothesis:

Assume $S(K)$ is true, $2^K > K^2$.

Then

$2^{K+1} = 2.2^K > K^2 + K^2$

I don't know how to proceed after this. How to complete this proof?

It's actually true for all $n\in\mathbb R$, $n>4$. You can show this by observing that the inequality is equivalent to $2^{1/2}>n^{1/n}$ and analyzing the function $f(x)=x^{1/x}$. — user236182, Aug 04 '16 at 18:28
The induction step is $2^{n+1}=2\cdot 2^n>2\cdot n^2=n^2+n^2>n^2+2n+1=(n+1)^2$ The last inequality follows from $n^2>3n=2n+n>2n+1$ — Peter, Aug 04 '16 at 18:34
If you really want to prove it for all real numbers $x>4$, I would suggest to take the logarthms and look at the function $\frac{x}{\ln(x)}$ — Peter, Aug 04 '16 at 18:53
Related proofs by induction are here and there. The first of these is noticeably stronger than what is required in the current Question. — hardmath, Aug 04 '16 at 19:06

score 2 · Accepted Answer · answered Aug 04 '16 at 18:33

2

You have: $2^{K+1} > 2K^2 > K^2 + 2K+1 = (K+1)^2$

answered Aug 04 '16 at 18:33

DeepSea

How did you reach $2K^2 > K^2 + 2K +1$? How did you get to that 2K+1 part? – piepi Aug 04 '16 at 18:35
@piepi You can show that when $K>4$, $K^2 > 4 K > 2K +1$. – harvey Aug 04 '16 at 18:49
So do I need to show 4K>2K+1 separately or is that implied because I don't think we have proved this relation yet? – piepi Aug 04 '16 at 19:06
1

$K^2 > 2K+1$ is quite clear because $K$ is a natural number $ \ge 3$. The case $K = 1,2$ can be checked easily. – DeepSea Aug 04 '16 at 19:10
@CHwC I don't follow. – piepi Aug 04 '16 at 19:45

1 Answers1