<s>[INST] Solving a recursion relation: $a_{n+1}=-3a_n+4a_{n-1}+2$ I'm having trouble solving this recursion relation. I believe it's a non-homogeneous one.
Here it is:
$$a_{n+1}=-3a_n+4a_{n-1}+2$$
Really, I am just having trouble with the particular solution.
The initial values are not specified.
Thanks!
 [/INST] My favorite way to solve these is with linear algebra:
$$\begin{align}
a_{n + 1}= -3a_n + 4a_{n-1} + 2 \\
a_{n} =     1a_n + 0a_{n-1} + 0 \\
\end{align}$$
$$\begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix} = 
\begin{bmatrix} -3 & 4 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} a_n \\ a_{n-1} \end{bmatrix}
 + \begin{bmatrix} 2 \\ 0 \end{bmatrix}
$$
$$\begin{bmatrix} a_{n+1} \\ a_n \\ 1 \end{bmatrix} = 
\begin{bmatrix} -3 & 4 & 2 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}
\begin{bmatrix} a_n \\ a_{n-1} \\ 1 \end{bmatrix}
$$
$$\begin{bmatrix} a_{n+1} \\ a_n \\ 1 \end{bmatrix} = 
\begin{bmatrix} -3 & 4 & 2 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^n
\begin{bmatrix} a_1 \\ a_0 \\ 1 \end{bmatrix}
$$
Although I prefer leaving it like this, you can use jordan decomposition:
$$\begin{cases}
P = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & -\frac 14 \\ 0 & \frac 52 & 0 \end{bmatrix} \\
D = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -4 \end{bmatrix} \\
\begin{bmatrix} a_{n+1} \\ a_n \\ 1 \end{bmatrix} = 
(P\,D\,P^{-1})^n
\begin{bmatrix} a_1 \\ a_0 \\ 1 \end{bmatrix}
\end{cases}
$$
$$\begin{bmatrix} a_{n+1} \\ a_n \\ 1 \end{bmatrix} = 
P\,\begin{bmatrix} 1 & n & 0 \\ 0 & 1 & 0 \\ 0 & 0 & (-4)^n \end{bmatrix}\,P^{-1}
\begin{bmatrix} a_1 \\ a_0 \\ 1 \end{bmatrix}
$$
$$
a_n = \frac 1{25}\bigg( a_1\,5\left(1 - (-4)^{n+1}\right) + a_0\,5\left(4 + (-4)^{n+1}\right) + 2(-4)^{n+1} + 10n + 8 \bigg)$$
</s>