Prove $m^3 \leq 2^m$ for $m \geq 10$ with induction

Question

Prove that $m^3 \leq 2^m$ for $m \geq 10$

This is my shot

Proof

We prove this by induction.

Basic step: For $n=10$ is $10^3 \leq 2^{10} = 1000 \leq 1024$ and that is correct.

Induction step: Assume that $k \geq 10$ and that the statement is true for each $10 \leq j \leq k$. We need to proof that it is also true for $k+1$.

So $$(k+1)^3 \leq 2^{k+1} \Rightarrow k^3 + 3k^2 + 3k + 1 \leq 2^k + 2^k \underbrace{\Rightarrow }_{\text{induction hypothesis}} 3k^2 + 3k + 1 \leq 2^k$$

Now I don't understand how I can prove the rest.

Answer 1

Your second equivalence is wrong. It has to be: $$k^3 + 3k^2 + 3k + 1 \leq 2^k + 2^k \impliedby k^3 \leq 2^k \land 3k^2 + 3k + 1 \leq 2^k$$

Now $k^3 \leq 2^k$ by the induction hypothesis.

For the last inequality, it is much easier to prove $3k^2+3k+1\leq k^3$, because $k^3 \leq 2^k$ by the induction hypothesis.

Now you just have to prove $-k^3+3k^2+3k+1\leq 0$ (for $k \geq 10$) which can be done by simple function analysis.

Answer 2

$$(k+1)^3 = k^3+3k^2+3k+1 \leq k^3+3k^2+3k^2+4k^2 = k^3+10k^2$$

From here, we use that $k\geq 10$

$$k^3+10k^2\leq k^3+k^3$$

Next, we use the induction hypothesis

$$k^3+k^3\leq 2^k+2^k=2^{k+1}$$

Answer 3

You have to prove $$m^3\le 2^m\implies (m+1)^3\le 2^{m+1}.$$

Taking the ratio,

$$\left(\frac{m+1}m\right)^3\le2\iff \frac{m+1}m\le\sqrt[3]2.$$

This inequality holds as soon as $m=4$.