I'm new to induction and have not done induction with inequalities before, so I get stuck at proving after the 3rd step.
The question is:
Use induction to show that $3^n > n^3$ for $n \geq 4$.
I have so far:
Step 1:
Prove for $n=4$ (since question states this)
$3^4 > 4^3$
$81 > 64 $
which is true
Step 2:
Assume true for $n=k$
$3^k > k^3$
Step 3:
Prove for $n = k+1$
$3^{k+1} > (k+1)^3$
Here I expand to:
$3^k \cdot 3 > k^3 + 3k^2 + 3k + 1$
However I have no idea how to prove this.
Thanks for any help given
$\endgroup$3 Answers
$\begingroup$$3^{k+1}>3k^3$
We need $3^{k+1}>(k+1)^3 $
So, it sufficient to prove $3k^3>(k+1)^3\iff \left(1+\frac1k\right)^3<3$
For $k=3,\left(1+\frac1k\right)^3=\frac{64}{27}<3$
and $\left(1+\frac1{k+1}\right)^3<\left(1+\frac1k\right)^3$
$\implies \left(1+\frac1k\right)^3<3$ for $k\ge3$
$\endgroup$ 2 $\begingroup$HINT: One approach is to compare ratios: on the left you’ve gone from $3^k$ to $3^{k+1}$, so you’ve multiplied by $3$, while on the right you’ve multiplied by
$$\frac{(k+1)^3}{k^3}=\left(\frac{k+1}k\right)^3=\left(1+\frac1k\right)^3=1+\frac3k+\frac3{k^2}+\frac1{k^3}\;.$$
How does this compare with $3$ when $k\ge 4$?
Added: Suppose that $a_n$ and $b_n$ are two quantities that depend on $n$, and you want to show by induction that $a_n>b_n$ for all $n\ge n_0$. You get your induction started by checking that $a_{n_0}>b_{n_0}$. For the induction step there are two very natural things to try.
Compare $a_{k+1}-a_k$ with $b_{k+1}-b_k$: if $a_k>b_k$ and $a_{k+1}-a_k\ge b_{k+1}-b_k$, then clearly $a_{k+1}>b_{k+1}$. You can check this by mechanical algebraic manipulation, but it should also be intuitively clear: you’ve added at least as much on the lefthand side as on the righthand side, and the lefthand side was already larger than the righthand side, so it remains larger.
Compare $\dfrac{a_{k+1}}{a_k}$ with $\dfrac{b_{k+1}}{b_k}$ and apply similar reasoning.
In both cases you’re comparing the growth rates of the two sides, in the first case additively and in the second case multiplicatively. Which of the two is more likely to succeed depends on the expressions involved; here the exponential suggests looking at the multiplicative version.
$\endgroup$ 2 $\begingroup$$3^n > n^3$ for $n\geq 4$
Base case: If $n=4$, we get $\text{LHS}=3^4=81$ $\text{RHS}=4^3=64$. We can see that $\text{LHS} > \text{RHS}$.
Let us assume the above hypothesis holds true for some $n=k$ such that $k\geq 4$. Therefore, $$3^k > k^3$$ $$3(3^k) > 3k^3$$ $$3^{k+1} > k^3 + k^3 + k^3 > k^3 + 3k^2 + 3k^2 > k^3 + 3k^2 + k^2 + k^2 + k^2 > k^3 + 3k^2 + 3k + 3k + 3k > k^3 + 3k^2 + 3k + 1 = (k+1)^3.$$
$\endgroup$ 1
