How to prove $n^3 < 4^n$ using induction?

Question

It's true for all Natural numbers.

What I've got so far: Prove $P(0) \to $ base case:

Let $n = 0$

$(0)^3 < 4^0 = 0 < 1$

Then $P(0)$ is true.

Part Two:

Prove $P(n) \Rightarrow P(n + 1) $

Assume $P(n)$

$= n^3 < 4^n $

$= 4(n + 1)^3 < 4^{(n + 1)}$

im not sure if the last step is right.

Where can I go from here?

Answer 1

Your last step is not right. You have $n^3<4^n$. Cool. Now take $(n+1)^3$ and expand it using the binomial theorem. You get $n^3+3n^2+3n+1$. You already know that $n^3<4^n$, so $n^3+3n^2+3n+1<n^3+n^3+n^3+1<4n^3<4\cdot 4^n=4^{n+1}$

Answer 2

If we know $n^3<4^n$ then $(n+1)^3=n^3+3n^2+3n+1<4^{(n+1)}=4^n+3(4^n)$ because $3n^2+3n+1<3(4^n)\iff n^2+n+\frac{1}{3}<4^n\iff n(n+1)+\frac{1}{3}<4^n$

We prove this last part by using inductive hypotesis and the fact $n(n+1)+\frac{1}{3}<n^3<4^n$ for $n>1$