Originally Posted by

**tukeywilliams** **5.2 **Prove by induction on $\displaystyle m $ that $\displaystyle m^{3} \leq 2^{m} $ for $\displaystyle m \geq 10 $.

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