<s>[INST] How to find a degree 2 homogeneous linear recurrence relation given a formula Given the formula $a_n = (-1)^n + 2^{n+1}$, how do you find a degree 2 homogeneous linear recurrence relation?
 [/INST] Let $a_{n+2} = a_{n+1}x + a_ny$. This gives
$$
(-1)^{n+2} + 2^{n+3} = ((-1)^{n+1} + 2^{n+2})x + ((-1)^n + 2^{n+1})y
$$
Separating this into two equations, one for the $-1$ term and one for the $2$ term, we get
$$
\cases{(-1)^{n+2} = (-1)^{n+1}x + (-1)^{n}y\\2^{n+3} = 2^{n+2}x + 2^{n+1}y}
$$
Dividing the first equation by $(-1)^n$ and the second by $2^{n+1}$, we get
$$
\cases{1 = -x+y\\4 = 2x + y}
$$
which may be solved for $x$ and $y$.
</s>