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!

We have $\displaystyle a_{n+1}+3a_n-4a_{n-1}-2=0$

Let $\displaystyle a_n=b_n+cn$ where $c$ is an arbitrary constant

$\displaystyle\implies b_{n+1}+c(n+1)+3\{b_n+cn\}-4\{b_{n-1}+c(n-1)\}-2=0$

$\displaystyle \implies b_{n+1}+3b_n-4b_{n-1}+c+4c-2=0$

We can safely set $\displaystyle c+4c-2=0\iff c=\frac25$ to eliminate the consonant from the recurrence relation

Then use this method

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)$$

Your problem here is that $a_n=a\cdot 1^n=a$ is a solution to the homogeneous equation (without the $2$ in it).

To see what to do put $b_n=a_n-a_{n-1}$ so that $b_{n+1}=-4b_n+2$, which has the particular solution $b_n=\frac 25$. This then gives $a_n=a_{n-1}+\frac 25=a_0+\frac 25\cdot n$ and a particular solution is seen to be $\frac 25\cdot n$.

The root $1$ of the auxiliary equation $x^2=-3x+4$ means that the test function for the particular solution should be $a\cdot n$ rather than just $a$. If the auxiliary equation had a double root $1$ - say the recurrence were $c_{n+1}=2c_n-c_{n-1}+2$ you'd need to use $c\cdot n^2$, because $a\cdot n+b$ is then a solution to the homogeneous part.