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?

 A: You need to gather more data first:
$$\begin{array}{rcc}
n:&1&2&3&4&5&6&7&8&9&10&11\\
n^3:&1&8&27&64&125&216&343&512&729&1000&1331\\
2^n:&2&4&8&16&32&64&128&256&512&1024&2048
\end{array}$$
Notice that $n^3$ is not less than $2^n$ for $n=2,3,\ldots,9$; the fact that $1^3<2^1$ is an isolated success. The simplest reasonable guess at this point is that $n^3<2^n$ if $n\ge 10$. Thus, the basis step for your induction will be the calculation that $10^3<2^{10}$.
For your induction step you’ll assume as induction hypothesis that $k^3<2^k$ for some integer $k\ge 10$. Your goal, then, will be to show that $(k+1)^3<2^{k+1}$. Note that
$$(k+1)^3=k^3\cdot\frac{(k+1)^3}{k^3}=k^3\left(\frac{k+1}k\right)^3\;.$$
Since $k\ge 10$, $\frac{k+1}k=1+\frac1k\le 1+\frac1{10}=\frac{11}{10}$, and therefore 
$$\left(\frac{k+1}k\right)^3\le\left(\frac{11}{10}\right)^3=\frac{1331}{1000}<2\;,$$
and therefore $(k+1)^3<2k^3$. By the induction hypothesis $k^3<2^k$, so ... ?
A: 
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.
A: Since the exponent of $n$ is more than $3$, $2^n$ will grow faster. Also both of them are monotonically increasing in $n$. So the answer is the first $n$  that satisfies $2^n > n^3$ and all $n$'s more than that. Obviously, for  $n=0,1$ it holds too.
for $n=10$ it obviously holds.
suppose $k^3 < 2^k   \Rightarrow \color{red} {(k+1)^3 <} 2k^3<2^{k+1}$ 
Now its your turn to prove ${(k+1)^3 <} 2k^3$
OK?
A: Hint:


*

*Consider $f(n) = n$ and $g(n) = \sqrt[3]{2}^n = 2^{\frac{n}{3}}$.

*For $n = 12$ we have $f(n) = 12 < 16 = g(n)$.

*Moreover, for $n > 12$, $g$ grows faster than $f$, that is, $f(n)-f(n-1) = 1 < 4 < 16(\sqrt[3]{2}-1) \leq g(n)-g(n-1)$.

*For $n \leq 12$ there are just a few cases.


I hope this helps ;-)
