<s>[INST] Proving a divisibility given a recurrence relation I am given the sequence $a_0 = 0$, $a_1 = 1$, and for all $n \geq 2$, $a_n = a_{n-1} + 2a_{n-2}$. I must prove that if $3 \mid n$, then $3 \mid a_n$. By logic, if $3 \nmid n$, then the conclusion $3 \mid a_n$ is automatically true. So, I should only prove that $3 \mid a_n$ is true for multiples of 3, right? So what I did was suppose $3 \mid n$ and try to prove that $3 \mid a_{3n}$. I will argue by induction on $n$.

*

*Base Case. Suppose $n = 0$. Then, $3 \mid 0 = a_0$. So, the base case holds.

*Induction Hypothesis Suppose $3 \mid a_{3k}$ for some integer $k \geq 0$. We must show that $3 \mid a_{3k+1}$.

I know that $a_{3k+1} = a_{3k} + 2a_{3k-1}$, which implies $a_{3k+1} = 3m + 2a_{3k-1}$ for some integer $m$. I don't know how to continue the proof from here. Is it even correct so far? Please help!
 [/INST] First strategy:
Let examine the three first terms $\begin{cases}a_0\equiv 0\pmod 3\\a_1\equiv 1\pmod 3\\
a_2= 1+2\times 0\equiv 1\pmod 3\end{cases}$
Now notice that $a_3\equiv 1+2\times 1\equiv 0\pmod 3$ like $a_0$
So the aim it to show by induction that the sequence of remainders is
$0,1,1,0,2,2,0,1,1,0,2,2,0,1,1\cdots$
Thus set as base hypothesis either $$P(n): a_{3n}\equiv 0\pmod 3,a_{3n+1}\equiv 1\pmod 3,a_{3n+2}\equiv 1\pmod 3$$
$$Q(n): a_{3n}\equiv 0\pmod 3,a_{3n+1}\equiv 2\pmod 3,a_{3n+2}\equiv 2\pmod 3$$
And go on to show that $a_{3n+3},a_{3n+4},a_{3n+5}$ follow the $0,2,2$ pattern if $P(n)$ is assumed and $0,1,1$ pattern if $Q(n)$ is assumed.

Second strategy:
$\begin{cases}a_{n+3}=a_{n+2}+2a_{n+1}\\a_{n+2}=a_{n+1}+2a_{n}\end{cases}\ $ now go on and replace $a_{n+2}$
Thus $\ a_{n+3}=3a_{n+1}+2a_n\ $ and it is immediate that if $3$ divides $a_n$ then $3$ also divides $a_{n+3}$
(because if $a_n=3k$ then $a_{n+3}=3(a_{n+1}+2k)$)
</s>