It can be verified that $$a_{n+2}=4a_{n+1} - a_n$$ Given $a_1=1$ and $a_2=4$ are integers, all $a_n$ will be integers too. Furthermore, we have $$a_{n+2}\equiv a_{n+1}-a_n \pmod{3}$$ Therefore, \begin{align*} & a_1\equiv 1&\pmod{3}\\ & a_2\equiv 1&\pmod{3}\\ & a_3\equiv (1-1)=0&\pmod{3}\\ & a_4 \equiv (0-1)\equiv 2&\pmod{3}\\ & a_5 \equiv (2-0) =2 &\pmod{3}\\ & a_6 \equiv (2-2) = 0 &\pmod{3}\\ & a_7 \equiv (0-2) \equiv 1&\pmod{1}\\ &\cdots \end{align*} Therefore, when $3|n$, we have $3|a_n$.