<s>[INST] Find the solution to the following non-homogenous recurrence relation: Find the solution to the following non-homogenous recurrence relation:
$a_{n+2} + a_{n+1} - 2a_n = n$ for $a_0 = 1$, $a_1 = -2$
I have found the homogenous part with the characteristic polynomial is
$a_n = C_1(-2)^n + C_2$ but don't know how to find the non-homogenous part?
Thanks in advance. 
 [/INST] One way is to find a difference equation that is solved by the function $n \mapsto  n$. If $b_n = n$, we see that $b_{n+1}-b_n = 1$ and so $b_{n+2}-2 b_{n+1} + b_n = 0$, with $b_0 = 0, b_1 = 1$.
Now let $x_n= (a_{n+1}, a_n, b_{n+1}, b_n)^T$, then we are looking for a solution to $x_{n+1} = A x_n$ where $A = \begin{bmatrix} -1 & 2 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 2 & -1 \\
0 & 0 & 1 & 0\end{bmatrix}$, and $x_0=(-2,1,1,0)^T$. We note that $A$ has an eigenvalue of multiplicity $3$ at $\lambda=1$ and an eigenvalue of multiplicity $1$ at $\lambda = -2$.
The solution is $x_n = A^n x_0$.
Rather than evaluating $A^n$ explicitly, since we are only interested in $a_n = e_2^T A^n x_0$, we use the eigenstructure of $A$ and assume that $a_n = C_1 (-2)^n + C_2 + C_3 n + C_4 n^2$. Since we know $a_0,a_1,a_2,a_3$, this gives four equations in $C_1,...,C_4$. Solving the equations gives $C_1 = \frac{32}{27}, C_2 = - \frac{5}{27}, C_3 = \frac{7}{18}, C_4 = \frac{1}{6}$, and so
$a_n = -\frac{{\left( -2\right) }^{n+5}}{27}+\frac{{n}^{2}}{6}+\frac{7\,n}{18}-\frac{5}{27}$.
</s>