Prove using Induction | Tricky one!

Question

I actually need some help. I want to prove using simple induction that
Q.1) $2^n > n^3$ for all $n \geq 10 $

I tried solving it like this...

Base Step:

$n = 10$:
$2^{10} > 10^3 = 1024 > 1000$ So, that's true and fine.

Inductive step:

Suppose $2^n > n^3$ is true for some $n$. So it means that it should also be true for $n+1$ So,

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

L.H.S:
$2^{n+1} = $?

Now here I'm stuck in further expanding this prove. I want to solve it further and make the $2^{n+1}$ with a power on top of it that I can use to compare with $n^3 + 3n^2 + 3n + 1$.

Kindly, tell me as easy as possible as I'm not expert in it. Thanks

Answer 1

Hint:

From the induction hypothesis, you deduce that $$2^{n+1}=2\cdot 2^n>2n^3,$$ hence by transitivity, it's enough to show that $2n^3\ge (n+1)^3$, or $\Bigl(1+\dfrac 1n\Bigr)^3\le2$.

Observe that $$\Bigl(1+\dfrac 1n\Bigr)^3=1+\frac3n+\frac3{n^2}+\frac1{n^3}\le 1+\frac9n\quad\text{(why?)}$$

Answer 2

What you have to prove is that, assuming $2^n>n^3$, $2^{n+1}>(n+1)^3$.

As $2^{n+1}=2\times2^n>2n^3$ by hypothesis, it suffices to prove that $2n^3>(n+1)^3$ for $n\ge10$.

One way to do this is study function $x\mapsto x^3-3x^2-3x-1$ and prove it takes positive values for $x\ge10$.

Answer 3

You already verified that $10^3 \lt 2^{10}.$

For the induction step, if $n^3\lt 2^n$ and $n\ge 10,$ then

\begin{align} (n+1)^3 &=\big(\frac{n+1}{n}\cdot n\big)^3 \\&=\big(1+\frac1{n}\big)^3 \cdot n^3 \\&\lt \big(1+\frac1{4}\big)^3 \cdot 2^n \scriptsize{\quad-\;\text{By (a) the fact that }n\gt 4\text{ and (b) the induction hypothesis.}} \\&=\big( \frac5{4}\big)^3 \cdot 2^n \\&=\frac{125}{64} \cdot 2^n \\&\lt \frac{128}{64} \cdot 2^n \\&= 2 \cdot 2^n \\&= 2^{n+1}. \end{align}