Showing that $a_n= 3^{n}+ 4^{n+1}+ 5^{n+2}$ is a solution of the recurrence relation $a_n = 12a_{n−1} − 47a_{n−2}+ 60a_{n−3}$ 
Let $a_n$ be given recursively by
$$a_n = \begin{cases} 30 & \text{if } n = 0\\\\ 144 & \text{if } n = 1\\\\ 698 & \text{if } n = 2\\\\ 12 a_{n−1} − 47 a_{n−2} + 60 a_{n−3} & \text{if } n \geq 3\\\end{cases}$$
Prove that $a_n= 3^{n}+ 4^{n+1}+ 5^{n+2}$. For which $n$ is $a_n$ divisible by $3$?

I honestly have no idea how to approach this. I started with brute force to obtain $a_3$ and $a_4$ as $3,408$ and $16,730$ but I do not see any pattern in the sequence. I think induction could be one approach. Right now, I'm learning about congruence classes so that might be another route but I don't know how I'd apply it.
 A: Hint: $x^3-12x^2+47x-60=(x-3)(x-4)(x-5)$
Let $Sa_n=a_{n+1}$ be the shift operator on sequences. Then. since $(S-a)\,a^n=0$, we have
$$
(S-3)(S-4)(S-5)\left(A\cdot3^n+B\cdot4^n+C\cdot5^n\right)=0
$$
A: First part
From characteristic polynomials point of view, the recurrence 
$$a_n=12a_{n-1}-47a_{n-2}+60a_{n-3}$$
has the following characteristic polynomial (as it was pointed by Jyrki Lahtonen in the comments)
$$x^3-12x^2+47x-60$$
which has the following roots $r_1=3, r_2=4,r_5=5$. Thus the general term of the recurrence is
$$a_n=Ar_1^n+Br_2^n+Cr_3^n=A\cdot3^n+B\cdot4^n+C\cdot5^n$$
Given the initial values, we have the following system of linear equations
$$\left\{\begin{matrix}
30=A+B+C
\\ 
144=A\cdot3+B\cdot4+C\cdot5
\\ 
698=A\cdot3^2+B\cdot4^2+C\cdot5^2
\end{matrix}\right.$$
which yields the following solution $A=1, B=4, C=25$. As a result:
$$a_n=3^n+4^{n+1}+5^{n+2}$$
Second part
$$3 \mid a_n \Leftrightarrow 3 \mid 4^{n+1}+5^{n+2}$$
But 
$$4 \equiv 1 \pmod{3} \text{ then } 4^{n+1} \equiv 1 \pmod{3}$$
$$5 \equiv -1 \pmod{3} \text{ then } 5^{n+2} \equiv (-1)^{n+2} \pmod{3} $$
Thus 
$$3 \mid 4^{n+1}+5^{n+2} \Leftrightarrow 3 \mid 1 + (-1)^{n+2}$$
which says for odd $n$, $3 \mid a_n$, but it also works for $n=0$.
