TAOCP 1.2.1 Exercise 10
Let $P(n)$ be the statement 2^n > n^3.
Section 1.2.1: Mathematical Induction
Exercise 10. [M22] Prove by induction that if $n \ge 10$, then $2^n > n^3$.
Verified: yes
Solve time: 37s
Solution
Let $P(n)$ be the statement
$$ 2^n > n^3. $$
We will prove by induction that $P(n)$ is true for all integers $n \ge 10$.
First, consider the basis step. When $n=10$,
$$ 2^{10}=1024 $$
and
$$ 10^3=1000. $$
Since
$$ 1024>1000, $$
the statement $P(10)$ is true.
Now assume inductively that $P(n)$ is true for some integer $n\ge10$; that is,
$$ 2^n>n^3. $$
We must prove that
$$ 2^{n+1}>(n+1)^3. $$
From the induction hypothesis,
$$ 2^{n+1}=2\cdot 2^n>2n^3. $$
Hence it suffices to prove that
$$ 2n^3\ge(n+1)^3 $$
for all $n\ge10$.
Expanding the cube,
$$ (n+1)^3=n^3+3n^2+3n+1. $$
Therefore
$$ 2n^3-(n+1)^3 =n^3-3n^2-3n-1. $$
Factor the first two terms:
$$ n^3-3n^2-3n-1 =n^2(n-3)-(3n+1). $$
Since $n\ge10$,
$$ n-3\ge7, $$
so
$$ n^2(n-3)\ge7n^2. $$
Also,
$$ 7n^2-(3n+1)>0 $$
for all $n\ge10$, because
$$ 7(10)^2-(3\cdot10+1)=700-31=669>0 $$
and the left-hand side increases with $n$.
Thus
$$ n^3-3n^2-3n-1>0, $$
hence
$$ 2n^3>(n+1)^3. $$
Combining this with
$$ 2^{n+1}>2n^3, $$
we obtain
$$ 2^{n+1}>(n+1)^3. $$
Therefore $P(n+1)$ is true.
By mathematical induction, $2^n>n^3$ for all integers $n\ge10$.
This completes the proof.
∎