I need help with verifying my solution for the homework question:
For the recurrence $a_{n+3}=a_{n+2}+a_{n+1}+a_n$ where $a_1=a_2=a_3=1$, prove that $a_n\leq 2^{n-2}$, $\forall n>1$
Hint: Use Second principle of induction
First off, I don't even know what is the second principle of induction defined as, so I came up with my own intuitive interpretation of it.
Here goes:
Let $P(k)$ be the statement that $a_n\leq 2^{n-2}$.
Base Case: Let us prove $P(2), P(3)$. $a_2=1\leq 2^{2-2}=1$ and $a_3=1\leq 2^{3-2}=2$.
Inductive Case: Let us prove that $P(k),P(k+1),P(k+2)\implies P(k+3)$. Assume $P(k),P(k+1),P(k+2)$ holds. Now, $a_{k+3}=a_{k+2}+a_{k+1}+a_k\leq 2^{k}+2^{k-1}+2^{k-2}=2^{k-2}(4+2+1)=2^{k-2}(7)\leq 2^{k-2}(8) =2^{k+1}\square$
My confusion comes because the second principle of induction tells us we need to use $P(1),P(2), \dots, P(n)$ to prove $P(n+1)$. However, I only used the previous 3 terms. Is that allowed?
I am also looking for more elegant answers as well! All help will be appreciated. I hope I have done enough research on this question by community standards!
Yes that is allowed as Mark Bennet says in his comment and your proof is almost correct.
$(1)\quad P(k)$ should be $a_k\le2^{k-2}$ (instead of $n$'s in the superscripts and subscripts) but I'm certain that's a typo.
$(2)\quad $To prove $P(4)$ is true using your inductive argument we need $P(1),P(2),P(3)$ to be true. But $a_1=1>{0.5=2^{1-2}}$. So $P(1)$ is false and you need to manually check that $P(4)$ is indeed true to use induction.