0
$\begingroup$

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!

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

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}$$

$\endgroup$
  • $\begingroup$ how did you get to line 2 of the working: ">k^3+3k2+3^2k"? $\endgroup$ – RandomMath Apr 17 '15 at 11:16
  • $\begingroup$ @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$. $\endgroup$ – mathlove Apr 17 '15 at 11:18
  • $\begingroup$ 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 $\endgroup$ – RandomMath Apr 28 '15 at 14:34
  • $\begingroup$ @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? $\endgroup$ – mathlove Apr 28 '15 at 21:38
1
$\begingroup$

$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$).

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I dont really understand what you are doing $\endgroup$ – RandomMath Apr 17 '15 at 11:00
  • $\begingroup$ 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 $\endgroup$ – WSL Apr 17 '15 at 11:03
  • 1
    $\begingroup$ @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. $\endgroup$ – String Apr 17 '15 at 11:04
  • $\begingroup$ @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? $\endgroup$ – RandomMath Apr 17 '15 at 11:25

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.