Define a recurrence relation and prove by induction.

Question

I am trying to answer the following question:

Define a recurrence relation by $a_0=a_1=a_2=2$ and $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ for $n\ge3$. Prove by induction: $a_n\le 2^n$ for all $n\ge1$.

Is it true that \begin{align} a_4 & = a_3+a_2+a_1\\ & =(a_2+a_1+a_0)+a_2+a_1\\ & = a_0+2a_1+2a_2\\ & = 2+4+4\\ & = 10? \end{align}

But by our result $a_4<8$, but this does not hold for $10<8$.

Could it be possible that $a_n<2^n$ for all $n>1$ is not true. Looking for clarification on this problem?

Answer 1

$a_3 = 2 +2 +2 = 6$, $a_4 = 6 + 2 +2 = 10$, and $2^4 = 16$, so the hypothesis holds.

To prove the hypothesis by induction, we have already proven it until $n=4$. Now, assume it holds for $n=1,..N$ and we want to prove it for $N+1$. Then:

\begin{align*} a_{N+1} &= a_N + a_{N-1} + a_{N-2}\\ &<2^N +2^ {N-1} +2^{N-2}\\ & = 2^2\times 2^{N-2} + 2 \times 2^{N-2} + 2^{N-2}\\ & = 7 \times 2^{N-2}\\ & < 8 \times 2^{N-2}\\ & = 2^{N+1} \end{align*}

Where the second line comes from the induction hypothesis.