<s>[INST] setting of this induction proof I would like to see if this is a correct induction proof and whether or not this is a good setting out of it
A sequence is defined by
$$a_n = a_{n-1} + a_{n-2} + a_{n-3}$$
for $n\geq 3, a_0 = 1, a_1 = 2, a_2 = 4$.
Prove that $a_n \leq 4^n$ for all $n\in\mathbb{N}$.  
Let $P(n)$ be the proposition that
$$''a_n\leq 4^n{''}.$$
Now since we have $a_0 = 1 = 4^0 \leq 4^0$ then $a_0 \leq 4^0$.
Also, $a_1 = 2 < 4 \leq 4 = 4^1$ then $a_1 \leq 4^1$.
Also, $a_2 = 4<16 = 4^2 \leq 4^2$ so $a_2 \leq 4^2$.  
Hence, $P(0),P(1),P(2)$ are true.  
Now, let $k-3\in\mathbb{N}$ and suppose $P(k-3),P(k-2),P(k-1)$ is true.
We must show that $P(k)$ is true.  
Now by definition
$$\begin{align}a_n &= a_{n-1} + a_{n-2} + a_{n-3} \\ &\leq 4^{n-1} + 4^{n-2} + 4^{n-3} \qquad \text{by the inductive hypothesis}\\ &= 21\times 4^{k-3} \\ &\leq 64\times 4^{k-3} \\ &= 4^{k}.\end{align}$$  
Hence, $P(k)$ is true if $P(k-3),P(k-2),P(k-1)$ is true for $k\geq 3$.
So by induction, $P(n)$ is true for all $n\in\mathbb{N}$.  
Would appreciate any advice.
 [/INST] Suppose that $P(n)$ is true and prove it for $P(n+1)$
$
a_n = a_{n-1} + a_{n-2} + a_{n-3}\quad $ by the inductive hypothesis
if we suppose that $P(k)$ is true for any $1\leq k\leq n$ we are using strong induction
We must prove that
$a_{n+1}\leq 4^{n+1}$
$a_{n+1}=a_n + a_{n-1} + a_{n-2} \leq 4^n+4^{n-1}+4^{n-2}=4^{n-2}\left(4^2+4+1\right)=21\cdot 4^{n-2}\leq 64\cdot 4^{n-2}=4^{n+1}$
proved
Hope this helps
</s>