Proof using strong induction 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.
 A: 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$
A: 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$.
A: 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$.
