Finals are coming up and I am wondering what I can add/ remove to perfect a proof using the principle of strong mathematical induction. I've done a proof as an example. Any feed back welcome.
Question
Let the sequence $a_0, a_1, a_2,...$ be defined by the following recursive definition: \begin{align*} a_0&=1,\\[1.5ex] a_1&=3,\\[1.5ex] a_2&=6,\\[1.5ex] a_k&=a_{k-1}+a_{k-2}+a_{k-3} \text{ for all integers $k \geq 3$} \end{align*} Use strong mathematical induction to prove that $a_n \leq 3^n$ for all integers $n \geq 0$
Proof
Let $P(n)$ be the predicate for $a_n \leq 3^n$. Thus, \begin{align*} P(0)&=a_o\leq 3^0 \rightarrow 1\leq 1\\[1.5ex] P(1)&=a_1\leq 3^1 \rightarrow 3\leq 3\\[1.5ex] P(2)&=a_2\leq 3^2 \rightarrow 6\leq 9\\[1.5ex] \end{align*} We can see that $P(0)$, $P(1)$ and $P(2)$ hold. Let us assume $P(i)$ holds for $0\leq i \leq k$ where $k\geq 2$. Consider $P(k+1)$: \begin{align*} a_{k+1}&=a_{k}+a_{k-1}+a_{k-2}\\[1.5ex] &\leq 3^k+3^{k-1}+3^{k-2}\\[1.5ex] &=3^2\cdot 3^{k-2}+ 3\cdot 3^{k-2}+ 3^{k-2}\\[1.5ex] &=3^{k-2}(3^2+3+1)\\[1.5ex] &\leq 3^{k-2}\cdot 3^3=3^{k+1} \end{align*} Since $P(k+1)$ holds for $k \geq 2$ we conclude that by the principle of strong mathematical induction, $a_n\leq 3^n$ holds $\forall n \geq 0$.