For what natural numbers is $n^3 < 2^n$? Prove by induction

Solution 1:

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 ... ?

Solution 2:

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.

Solution 3:

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?