Induction proof for expression $4^n > n^3$

Question

I'm trying to proof that expression $(4^n>n^3)$ for $n\in \mathbb{N}$ using the induction.

1.There is $n0 = 0 $ for what $L=4^0=1$ and $P=n^0=0$

That is why $L>P$

---

2.Let's see what happen for $n+1$

Assumption: $4^n > n^3$ Thesis: $4*4^n > (n+1)^3$

I was always doing it like that $L = 4*4^n$ due to the assumption is greater than $4 * n^3$

And I do not know how can I solve it.

Answer 1

The bases case $n = 1, 2$ are clear since $4^1 = 4 > 1 = 1^3, 4^2 = 16 > 8 = 2^3$. Assume the statement is true when $n = k\geq 3$, you prove its true for $n = k+1$. This means to prove: $4^{k+1} > (k+1)^3$. We have: $4^{k+1} = 4\cdot 4^k > 4\cdot k^3 = k^3 + k^3+k^3+k^3 \geq k^3+3k^2 + 3k+ 1 = (k+1)^3$. Thus its true for all $n \geq 1$.

Answer 2

You want to show that if $4^n > n^3$ then $4 * 4^n > (n + 1)^3$.

If n ≥ 2 then $(1 + 1/n)^3 ≤ 1.5^3 = 3.375 < 4$. This shows that $(n + 1)^3 ≤ 3.375 n^3$ for n ≥ 2.

If n ≥ 2 then $4^{n+1} = 4 * 4^n > 4 * n^3 ≥ 3.375 n^3 ≥ (n+1)^3$.

Since $4^n > n^3$ is true for n = 1 and n = 2, it is true for all n.