# Proof by Induction $3^n > n^3$

I am trying to prove the following, however I'm stuck at the Induction hypothesis

Prove by induction that, for all integers $n$, if $n\geq 5$, then $3^n>n^3$

What I have Done:

Base Case: $n = 5$

$3^5 > 5^3$

$243 > 125$ so TRUE

Assume True for $n = k$

$3^k > k^3$ must be TRUE

Should be TRUE for $n = k+1$

$3^k + 3^{k+1} > k^3 + 3^{k+1}$

Im a little stuck here. Any help would be appreciated!

• The inequality holds for all nonnegative integer $n\neq 3$. – Alex Silva Apr 17 '15 at 11:11

Supposing that $3^k\gt k^3$, you need to prove $3^{k+1}\gt (k+1)^3$.

For inductive step : \begin{align}3^{k+1}&\gt 3k^3\\&=k^3+k^3+k^3\\&\gt k^3+3k^2+3^2k\\&=k^3+3k^2+3k+6k\\&\gt k^3+3k^2+3k+1\\&=(k+1)^3.\end{align}

• how did you get to line 2 of the working: ">k^3+3k2+3^2k"? – RandomMath Apr 17 '15 at 11:16
• @RandomMath: Because of $k\gt 3$. See $k^3=k\cdot k\cdot k\gt 3\cdot k\cdot k=3k^2$ and $k^3=k\cdot k\cdot k\gt 3\cdot 3\cdot k=3^2k$. – mathlove Apr 17 '15 at 11:18
• Would you be able to show the way you did in the inductive step how you got to $k^3+3k^2+3^2k$? It doesn't seem to be making much sense – RandomMath Apr 28 '15 at 14:34
• @RandomMath: Well, I already wrote how to get it in the above comment. Since we have $k^3\gt 3k^2$ and $k^3\gt 3^2k$ which I wrote how to get, we have $k^3+k^3+k^3\gt k^3+3k^2+3^2k$. This is how I got it. Or do you mean why? – mathlove Apr 28 '15 at 21:38

$3^{k+1}=3*3^k\geq 3k^3$ and it's easy to check that $(k+1)^3\leq 3k^3$ since $3k+1\leq 4k \leq k^3$ and $3k^2\leq k^3$ (because $k\geq 5$).

Your third equations is wrong, I think you are confused with summation induction proofs, you need to prove: $$3^{k+1}>(k+1)^3$$ You don't need to prove (anyways it will hold true either ways): $$3^k+3^{k+1}>k^3+k^{3+1}$$

By induction, you assume that for $n = k, 3^k > k^3$ must be true. We want to show $3^{k+1} > (k+1)^3$.

Thus, $3^{k+1} = 3^k\cdot 3 >3\cdot k^3$, by your induction hypothesis.

So we want to show $3^{k+1} > (k+1)^3$, but have $3^{k+1} > 3k^3$.

So just show $3k^3 > (k+1)^3$ for $k>5$. We have

$(k+1)^3 = k^3+3k^2+3k +1 < k^3+k^3+k^3 = 3k^3$.

Therefore,$3^{k+1} > 3k^3 > (k+1)^3 \Longrightarrow 3^{k+1} > (k+1)^3,$

and we are done.

• I dont really understand what you are doing – RandomMath Apr 17 '15 at 11:00
• So the point of induction is to use the assumption $3^k > k^3$ to derive the statement $3^{k+1} > (k+1)^3$. My second line shows how you relate these two statments. I'll fill in some details – WSL Apr 17 '15 at 11:03
• @RandomMath: How is that comment supposed to bring you anywhere nearer to a solution? If you feel uncertain about a specific step (could be the first step), then ask for clarification. – String Apr 17 '15 at 11:04
• @WSL The line I'm most confused on is line 5, where "(k+1)3=k3+3k2+3k+1<k3+k3+k3=3k3." Could you please elaborate on what you did? – RandomMath Apr 17 '15 at 11:25