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!
 A: 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)$)
A: As zwim pointed out, the pattern of $a_n$ mod $3$ is $0,1,1,0,2,2,0,1,...$.
Since $a_n$ can be expressed in terms of $a_{n-1}$ and $a_{n-2}$,
once we obtain $0,1$ again, the pattern continues.
Alternatively, you could solve the recurrence to get that $a_n=\dfrac{2^n-(-1)^n}3$
and show that $2^{3m}+1\equiv0\pmod9$ for $m$ odd and $2^{3m}-1\equiv0\pmod9$ for $m$ even,
since $2^6\equiv1\pmod9$.
A: $$\begin{align}\bmod 3\!: \ 
&\ a_{n+2}-a_{n+1}+a_{n}\equiv 0\\[.3em]
\iff\ \  & (S^2-S+1) a_n\equiv 0,\,\ S(a_n) := a_{n+1}\\
\overset{\!\!\times\ (S+1)}\Longrightarrow \ \ \  &(S^3+1) a_n\equiv 0,\ \ {\rm i.e.}\ \ \bbox[5px,border:1px solid #c00]{a_{n+3}\equiv -a_n}\\[.3em]
\color{#c00}{\rm thus}\ \ \ \ \ &\ a_0\equiv 0\,\Rightarrow\ a_3\equiv 0\,\Rightarrow\,a_6\equiv 0\,\cdots\,\Rightarrow a_{3n}\equiv 0
\end{align}\qquad\qquad\qquad $$
Passing from $\,S^2\!-\!S\!+\!1\,$ to its multiple $\,S^3\!+1$ is an instance of the method of simpler multiples, in an "operator algebra": polynomials in $S$ generated by a linear shift operator $\,S\:\!f(n) = f(n\!+\!1)$.
