Solve the recurrence relation $a_n - 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$ Solve the recurrence
$a_n - 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$
with initial conditions $a_1 = 1, a_2 =5$ and $a_3 = 17$ How this was calculated? any hint or idea highly appreciated
 A: Hint: I'd suggest using characteristic polynomials. This particular recurrence can be made  homogeneous linear from:
$$a_n - 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$$
$$a_{n-1} - 5a_{n-2} +8a_{n-3} -4a_{n-4} = 3^{n-1}$$
and
$$a_n - 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$$
$$3a_{n-1} - 15a_{n-2} +24a_{n-3} -12a_{n-4} = 3^n$$
and subtracting
$$a_n-8a_{n-1}+23a_{n-2}-28a_{n-3}+12a_{n-4}=0$$
which leads to the following characteristic polynomial:
$$x^4-8x^3+23x^2-28x+12=0$$
Integers solutions (if any, rational roots theorem) should be divisors of $12$ and indeed $1,2,3$ are the solutions. Or
$$x^4-8x^3+23x^2-28x+12=(x-1)(x-2)^2(x-3)$$
Everything else is mechanics, here and here are a few examples to help you finish the exercise.
A: Let $a_n=b_n \, 3^n$ to make
$$b_n-\frac{5}{3} b_{n-1}+\frac{8}{9} b_{n-2}-\frac{4}{27} b_{n-3}=1$$ Now, make $b_n=c_n+k$ to make
$$c_n-\frac{5}{3} c_{n-1}+\frac{8}{9} c_{n-2}-\frac{4}{27} c_{n-3}=1-\frac{2 k}{27}$$ Chose $k=\frac{27}{2}$ to make the rhs equal to $0$.
Solve
$$c_n-\frac{5}{3} c_{n-1}+\frac{8}{9} c_{n-2}-\frac{4}{27} c_{n-3}=0$$ When done, go back to $b_n=c_n+\frac{27}{2}$ and to $a_n=b_n \, 3^n$.
