# Proof using strong induction [duplicate]

This question already has an answer here:

I need to prove/show that $n^3 \leq 3^n$ for all natural numbers $n$ by strong induction. I have no clue where to begin!!!! :( I know how to do the beginning steps of showing that it's true for $k = 0$ and $k = 1$, etc but get suck on how to start the strong inductive step.

## marked as duplicate by Daniel W. Farlow, drhab, Community♦Mar 11 '15 at 9:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Interesting. I wonder why the closing because of duplicate vote didn't render that math display properly...smh – Daniel W. Farlow Mar 11 '15 at 8:30
• @crash It converted the < into &gt;, which isn't correct LaTeX markup. – Najib Idrissi Mar 11 '15 at 8:47
• @NajibIdrissi Since the conversion is automated, shouldn't it account for that? – Daniel W. Farlow Mar 11 '15 at 8:48

## 3 Answers

We can prove that $n^3 < 3^n$ for all $n\geq 4$ (which is basically the same thing as proving that $n^3 \leq 3^n$ for $n\geq 0$), and we can prove this using weak induction (there's no need to use strong induction here).

Start by noting that $$3n^2+3n+1<2(3^n)\tag{1}$$ is true for $n\geq 4$. One can verify $(1)$ using induction or, more cumbersomely, in a direct fashion.

Claim: For $n\geq 4$, $$n^3 < 3^n.$$

Proof. For $n\geq 4$, let $P(n)$ denote the proposition $$P(n) : n^3 < 3^n.$$

Base step ($n=4$): Since $4^3=64<81=3^4$, the statement $P(4)$ is true.

Inductive step: Suppose that for some fixed $k\geq 4$, $$P(k) : k^3 < 3^k$$ holds. It must be shown that $$P(k+1) : (k+1)^3 < 3^{k+1}$$ follows. Starting with the left-hand side of $P(k+1)$, \begin{align} (k+1)^3 &= k^3+3k^2+3k+1\\[0.5em] &< 3^k+3k^2+3k+1\tag{by $P(k)$}\\[0.5em] &< 3^k+2(3^k)\tag{by $(1)$}\\[0.5em] &= 3(3^k)\\[0.5em] &= 3^{k+1}, \end{align} we end up with the right-hand side of $P(k+1)$. Thus, $P(k+1)$ is also true, and this concludes the inductive step $P(k)\to P(k+1)$.

Thus, by mathematical induction, $P(n)$ is true for all $n\geq 4$. $\blacksquare$

• Ok I'm stuck on how you got (1)??? I've been tryiny to figure it out but I can't figure out any manipulation to get to 2*(3^n) < 3n^2+3n+1! – Melissa Mar 12 '15 at 23:33
• @Melissa Try using induction :) – Daniel W. Farlow Mar 13 '15 at 0:17
• Well I know I could prove that by using induction but why did you claim that to begin with is my curiosity. And this is for a class so I want to make sure I understand the reasoning so I can do well on the tests. Why the 2?? – Melissa Mar 13 '15 at 0:40
• @Melissa I used that inequality because I realized I needed it in the proof of your originally inequality. There's really not much more to it than that. Sometimes in inductive proofs you have to proof several small sub cases or use several inequalities that you have to prove independently. You can think of it as "working backwards" in a sense. – Daniel W. Farlow Mar 13 '15 at 0:48
• ok I thought I could prove that step on my own using induction but now I'm getting stuck. This is what I started with and the last line is where I get stuck. Any direction/hints?? (After taking care of the basis and I.H. I proceeded with the following). Need to show: 3(n+1)^2 + 3(n+1) + 1 <= 2(3^(n+1)) – Melissa Mar 15 '15 at 1:43

For the strong inductive step, you want to assume:

$$k^3 \le 3^n$$

and use that to prove

$$(k+1)^3 \le 3^{n+1}$$

Use the fact that $a < b$ and $b < c$ implies $a < c$.

Assume true for $n=k$. Now let's try for $n=k+1$, \begin{align*} (k+1)^3 &=k^3+3k^2+3k+1 \\ &\leq 3^k + 2k^3 \\ &\leq 3^k+2 \cdot 3^k=3^{k+1} \end{align*} where the second step used $2k^3-3k^2-3k-1 =k^3+(k-1)^3-6k \geq 0$ (for $k\geq 3$) and the second and third step used the assumption that $k^3 \leq 3^k$.

P.S. you would need to check the beginning steps up to $n=3$.