4
$\begingroup$

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$
6
$\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$
  • $\begingroup$ Thanks for this, I understand now $\endgroup$ – Alexander North Sep 24 '13 at 18:45
  • $\begingroup$ @LlamaGoingNorth, my pleasure $\endgroup$ – lab bhattacharjee Sep 24 '13 at 18:46
3
$\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.

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

  2. 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$
  • $\begingroup$ @LlamaGoingNorth: The lefthand side grows by a factor of $3$ when you go from $k$ to $k+1$; if the lefthand side at $k$ is bigger then the righthand side, and the righthand side grows by a factor of $3$ or less when you go from $k$ to $k+1$, then the new lefthand side will be larger than the new righthand side. $\endgroup$ – Brian M. Scott Sep 24 '13 at 18:45
  • $\begingroup$ @LlamaGoingNorth: Excellent! You’re welcome. $\endgroup$ – Brian M. Scott Sep 24 '13 at 18:51
1
$\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
    $\begingroup$ I fixed your formatting. In future please try to do yourself. $\endgroup$ – Nex Aug 17 '16 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.