# Check my solution: 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}$.

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!

• Using this principle you have available all the previous values. You use three of the ones you have available. – Mark Bennet Aug 8 '15 at 11:28
• What you are describing as the "second principle of induction" is also called the "strong form" of mathematical induction. Yes, it allowed to call a proof that uses three of the previous values a proof that "uses" this principle (or even if uses only one; the "strong form" includes the "weak form" as a special case). – hardmath Aug 8 '15 at 11:34

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