All solutions of the recurrence relation

Question

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-219}-64a_{n-3}+k $$

Answer 1

Plug $a_n=b^n$ into the above equation, ignoring the RHS, and get that $b$ satisfies

$$b^3-2 b^2-15 b+36=0 $$

Solutions are $b=3$ (double root) and $b=-4$. The general homogeneous solution is then

$$a_n = (A+B n) 3^n + C (-4)^n $$

For the particular solution, plug in $a_n = D \cdot 2^n$ and get that

$$D \left (1 - 1 - \frac{15}{4} + \frac{36}{8} \right ) 2^n = 2^n \implies D = \frac{4}{3} $$

Thus, the general solution is

$$a_n = (A+B n) 3^n + C (-4)^n + \frac{4}{3} 2^n$$