6
$\begingroup$

Problem

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

Attempt @ Solution

  1. For $n=1$, $1 < 2$
  2. Suppose $n^3 < 2^n$ for some $n = k \ge 1$
  3. It looks like the inequality is true for $n = 0$, $n = 1$ and $n\ge10$
  4. But, how can I prove this through induction?
$\endgroup$
4

4 Answers 4

13
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ ...so (k+1)^3 < 2^{k+1}! $\endgroup$
    – user86994
    Jul 20, 2013 at 8:07
  • $\begingroup$ @Thomas: That’s exactly right. (Note that $\left(\frac{k+1}k\right)^3$ is actually less than $2$ already when $k=4$, so the induction step actually works for $k\ge 4$, but we can’t get the basis step to work until we get up to $k=10$.) $\endgroup$ Jul 20, 2013 at 8:16
11
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can you explain how you transformed $3k +1$ into $9k+10$ ? $\endgroup$
    – Trey
    Dec 28, 2019 at 23:12
1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Thanks! I see that the inequality is true for $n>=10$, however, how can I prove this through induction? $\endgroup$
    – user86994
    Jul 20, 2013 at 7:26
0
$\begingroup$

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 ;-)

$\endgroup$

You must log in to answer this question.