The art of computer science - Mathematical Induction

Question

Please help me with section 1.2.1 question number 10:

Prove by induction that if $n \ge 10$ then $2^n > n^3$.

I managed to get so far:

for $n+1$ I get: $2^{n+1} = 2\cdot 2^n > 2n^3$

And now I need to prove that:

$2n^3 > (n+1)^3$

Then I get:

$n^3 > 3n^2 + 3n +1$

And I don't manage to solve it from here

Answer 1

Note

$n > 1, n> 4$ so

So for the induction step:

Assuming $2^n > n^3$ then

So $(n+1)^3 = n^3 + 3n^2 + 3n + 1 <$

$n^3 + 3n^2 + 3n + n = n^3 + 3n^2 + 4n < $

$n^3 + 3n^2 + n^2=n^3 + 4n^2 < $

$n^3 + n^3 = 2(n^3) <$

$2(2^n) = 2^{n+1}$.

That's it.

If somehow you want to go forward...

Well

$2^{n+1} = 2*2^n > 2*n^3 = n^3 + n^3 >$

$n^3 + 4*n^2 = n^3 + 3n^2 + n^2 > $

$n^3 + 3n^2 + 4n = n^3 + 3n^2 + 3n + n > $

$n^3 + 3n^2 + 3n + 1 = (n +1)^3$.

Although it's nice to drive forward, I prefer to be able to see which direction to steer.

Answer 2

We have to prove that $$2^{n+1}>(n+1)^2$$ if $$2^n>n^3$$ Multiplying this inequality by $2$ we get $$2^{n+1}>2n^3$$. Now you must show that $$2n^3>(n+1)^3$$ This gives $$n^3-3n^2-3n-1>0$$ which is true for $n\geq 10$. $$n^3-3n^2-3n-1=0$$ if $n\approx 3.847322102$