I have a question that is for a homework assignment and I just would like to ask if I seem to be on the right track or if I'm just doing it completely wrong.
Here is the question:
The sequence $\{a_n\}$ is defined by: $a_0 = 1$, $a_1 = 2$, $a_2 = 3$, and $a_n = a_{n-1} + 3a_{n-3} +3$ for all integers $n \geq 3$. Use strong mathematical induction to prove that $a_{n} \leq 2^{n}$ is true for all integers $n \geq 5$. Make sure you make reference to the fact that $n \geq 5$.
First off, here is what I calculated for the first few terms to get an idea. $\begin{align*} a_{3} &= a_{2} + 3a_{0} + 3 = 3 + 3(1) + 3 = 9 \\ a_{4} &= a_{3} + 3a_{1} + 3 = 9 + 3(2) + 3 = 18 \\ a_{5} &= a_{4} + 3a_{2} +3 = 18 + 3(3) +3 = 30 \end{align*}$
Here is my attempted solution:
For $n=5$, $a_{5} = a_{4} + 3a_{2} + 3 = 30$, for $n=6$, $a_{6} = a_{5} + 3a_{3} +3 = 60$, and finally for $n=7$, $a_{7} = a_{6} + 3a_{4} + 3 = 120$. By strong induction, assume that $a_{i} \leq 2^{i}$ for some $i$ in which $5 \leq i \leq k$, where $k \in \mathbb{Z}$. We want to prove that $a_{k+1} \leq 2^{k+1}$, meaning we want to show $a_{k} + 3a_{k-2} + 3 \leq 2 (2^{k})$. Provided that $k-2 \geq 5$, which it is, by our assumption we know that $a_{k-2} \leq 2^{k-2}$; which is that $a_{k-3} + 3a_{k-5} +3 \leq \frac{2^{k}}{4}$. Since, $a_{k+1} = a_{k} + 3a_{k-2} + 3 = a_{k} + 3(a_{k-3} + 3a_{k-5} +3) + 3$ ... and I have no idea where to go after this.
I've gone down a bunch of dead end roads and I see that there is a substitution available (I see the part of $a_{k-2}$ that I what to sub in of $a_{k+1}$ but I don't know how to make it work! Any tips would be appreciated. (Not looking for someone to just solve the problem for me).
--
I believe I have solved the proof, can you let me know if this looks better?
Proof: For $n=5$, $a_{5} = a_{4} + 3a_{2} + 3 = 30$ and $2^{5} = 32$, so $a_{5} \leq 2^{5}$ is true as $30 \leq 2^{32}$. Additionally, for $n=6$, $a_{6} = a_{5} + 3a_{3} +3 = 60$ and $2^{6} = 64$,so $a_{6} \leq 2^{6}$ is true as $60 \leq 64$. Finally for $n=7$, $a_{7} = a_{6} + 3a_{4} + 3 = 120$ and $2^{7} = 128$, so $a_{7} \leq 2^{7}$ is true as $120 \leq 128$. By strong induction, assume that $a_{i} \leq 2^{i}$ for all $i$ in which $5 \leq i \leq k$, where $k \in \mathbb{Z}$. We want to prove that $a_{k+1} \leq 2^{k+1}$, meaning we want to show $a_{k} + 3a_{k-2} + 3 \leq 2 (2^{k})$. Since in our basis step we have shown that $a_{7} \leq 2^{7}$, we can assume that $k \geq 7$, or in other words that $k-2 \geq 5$. Thus, by our assumption, we know that $a_{k-2} \leq 2^{k-2}$; and since we know that $k-2 \geq 5$ we can say $k \geq 5$, so we also know that $a_{k} \leq 2^{k}$. Then, $\begin{align*} a_{k+1} &= a_{k} + 3a_{k-2} + 3\\ &\leq 2^{k} + 3(2^{k-2}) + 3 \\ &\leq 2^{k} + 4(2^{k-2}) - 2^{k-2} +3 \\ &\leq 2^{k} + 2^{k} - 2^{k-2} +3 \\ &\leq 2^{k} + 2^{k} \\ &\leq 2^{k+1} \end{align*}$ Observe that even in the minimal case when $k=5$, $-2^{k-2} +3 < 0$ as $- 2^{5-2} + = -4 < 0$, so $a_{k+1} \leq 2^{k+1}$, which was what we wanted to prove for the induction step. Therefore, by the Strong Principle of Mathematical Induction, for all integers $n \geq 5$, $a_{n} \leq 2^{n}$.