<s>[INST] For what natural numbers is $n^3 < 2^n$? Prove by induction Problem
For what natural numbers is $n^3 < 2^n$?
Attempt @ Solution


*

*For $n=1$, $1 < 2$

*Suppose $n^3 < 2^n$ for some $n = k \ge 1$

*It looks like the inequality is true for $n = 0$, $n = 1$ and $n\ge10$

*But, how can I prove this through induction?

 [/INST] 
Claim: If $n \in \{0,1\} \cup \{n \in \Bbb{N} \mid n \ge 10\}$, then $n^3<2^n$.

You have verified the claim for $n=0$ and $n=1$. The next time the inequality holds is at $n=10$, since $10^3=1000<1024=2^{10}$. This is our base case.
Induction Hypothesis: Assume that $n^3<2^n$ holds true for $n=k\ge10$.
It remains to prove the claim true for $n=k+1$. Observe that since $10 \le k$, we have:
$$ \begin{align*}
(k+1)^3 &= k^3+3k^2+3k+1 \\
&< k^3+9k^2+9k+10 \\
&\le k^3+9k^2+9k+(k) \\
&= k^3+9k^2+10k \\
&\le k^3+9k^2+(k)k \\
&= k^3+10k^2 \\
&\le k^3+(k)k^2 \\
&= 2k^3 \\
&< 2(2^k) & \text{by the induction hypothesis}\\
&= 2^{k+1}
\end{align*} $$
as desired. This completes the induction.
</s>