# Define a recurrence relation and prove by induction.

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?

• Welcome to MSE. For tips on how to format etd see tutorial. You will get a better response if it is properly formatted. – almagest Sep 25 '19 at 16:05
• It should be $$10 = a_4 < 2^4 = 16$$so it's true. – Max Wong Sep 25 '19 at 16:06
• Also people here hate images when not strictly necessary. Please include question directly. I have just done it for you this time. – almagest Sep 25 '19 at 16:14

$$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*}