Proof using strong induction

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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$