Recurrences part 3

See, it's not that tough as it looks, very easy !!!

$a_n = 7 a_{n-1} -10a_{n-2} +3^n .......... eq (1)$

$a_{n-1} = 7a_{n-2}-10a_{n-3} +3^{n-1}$

Hence $3a_{n-1} = 21a_{n-2}-30a_{n-3} +3^n..........eq(2)$

---

Subtract the 2 equations to get

$a_n-3a_{n-1} = 7a_{n-1} -31 a_{n-2} +30a_{n-3}$

That is $a_n - 10a_{n-1} +31a_{n-2} -30a_{n-3} = 0$

Characterstic equation is $x^3-10x^2+31x-30=0$ That is $(x-2)(x-5)(x-3) =0$

And thus each term can be written as $a_n = x 2^n +y3^n+z3^n$

We have initial conditions $a_0=0 , a_1=1$ and calculating from the recurrence , $a_2 = 16$

Thus you get 3 equations with 3 variables ,

$0 = x+y+z$ $1= 2x+3y+5z$ $16 = 4x+9y+25z$

Solve to get $x = \dfrac{8}{3}, y = \dfrac{-9}{2} , z = \dfrac{11}{6}$

Hence general term is given by $a_n = \frac{8}{3} 2^n -\frac{9}{2} 3^n +\frac{11}{6} 5^n$

Thus $a_{20} =\frac{8}{3} \cdot 2^{20} -\frac{9}{2} \cdot 3^{20} +\frac{11}{6} \cdot 5^{20} =174824603607544$

Hence the last 3 digits are $\boxed{544}$