# Math Help - Induction: Look correct?

1. ## Induction: Look correct?

5.2 Prove by induction on $m$ that $m^{3} \leq 2^{m}$ for $m \geq 10$.
Proof: We use induction on $m$. Base case: For $n = 10$, $m^{3} = 1000$ and $2^{10} = 1024$ and so $m^{3} \leq 2^{m}$. Inductive step: Suppose now as inductive hypothesis that $k^{3} \leq 2^{k}$ for some $k \geq 10$. Then $2^{k+1} = 2 \times 2^{k} \geq 2k^{3}$ (by induction hypothesis). So we will have proved that $2^{k+1} \geq (k+1)^{3}$ if we can prove that $2k^{3} \geq (k+1)^{3}$. But $2k^{3} \geq (k+1)^{3} \Leftrightarrow 2k^{3} \geq k^{3} + 3k^{2} + 3k + 1 \Leftrightarrow k^{3} \geq 3k^{2} + 3k + 1$, and since $k \geq 10$, $k^{3} \geq 10k^{2} \geq 3k^{2} + 3k + 2 \geq 3k^{2} + 3k + 1$ so that $k^{3} \geq 3k^{2} +3k+1$. Hence $2k^{3} \geq (k+1)^{3}$ and so we have deduced that $(k+1)^{3} \leq 2^{k+1}$ as required to complete the inductive step. Conclusion: Hence, by induction, $m^{3} \leq 2^{m}$ for all $m \geq 10$. $\square$

2. Originally Posted by tukeywilliams
$m^{3} \leq 2^{m}$.
You wish to show this for $m\geq 10$.

Say it is true for $m=k$, i.e. $k^3 \leq 2^k$.

Then, multiply both sides by 2,
$2k^3 \leq 2 \cdot 2^m = 2^{m+1}$
Now if you can show that,
$(k+1)^3 \leq 2k^3$
5.2 Prove by induction on $m$ that $m^{3} \leq 2^{m}$ for $m \geq 10$.
Proof: We use induction on $m$. Base case: For $n = 10$, $m^{3} = 1000$ and $2^{10} = 1024$ and so $m^{3} \leq 2^{m}$. Inductive step: Suppose now as inductive hypothesis that $k^{3} \leq 2^{k}$ for some $k \geq 10$. Then $2^{k+1} = 2 \times 2^{k} \geq 2k^{3}$ (by induction hypothesis). So we will have proved that $2^{k+1} \geq (k+1)^{3}$ if we can prove that $2k^{3} \geq (k+1)^{3}$. But $2k^{3} \geq (k+1)^{3} \Leftrightarrow 2k^{3} \geq k^{3} + 3k^{2} + 3k + 1 \Leftrightarrow k^{3} \geq 3k^{2} + 3k + 1$, and since $k \geq 10$, $k^{3} \geq 10k^{2} \geq 3k^{2} + 3k + 2 \geq 3k^{2} + 3k + 1$ so that $k^{3} \geq 3k^{2} +3k+1$. Hence $2k^{3} \geq (k+1)^{3}$ and so we have deduced that $(k+1)^{3} \leq 2^{k+1}$ as required to complete the inductive step. Conclusion: Hence, by induction, $m^{3} \leq 2^{m}$ for all $m \geq 10$. $\square$