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. 
 A: Here is a solution using generating functions. Put $$A(z) = \sum_{n\ge 0} a_n z^n$$
and multiply the recurrence
$$a_{n+2}+a_{n+1}-2a_n = n$$
by $z^{n+2}$ and sum over $n\ge 0$ to get
$$\sum_{n\ge 0} a_{n+2} z^{n+2} 
+ \sum_{n\ge 0} a_{n+1} z^{n+2}
- 2\sum_{n\ge 0} a_n z^{n+2}  = \sum_{n\ge 0} n z^{n+2}.$$
This gives
$$A(z) - a_1 z - a_0 
+ z (A(z) - a_0) -  2 z^2 A(z) = \sum_{n\ge 1} n z^{n+2}.$$
Further simplification yields
$$ A(z) ( 1 + z - 2 z^2)  - (a_0+a_1) z - a_0 = z^3 \sum_{n\ge 1} n z^{n-1}
= z^3 \frac{1}{(1-z)^2}.$$
Solve this for $A(z)$ and subsitute the values $a_0 = 1$ and $a_1 = -2$ to get
$$ A(z) =-{\frac {7}{9}}\, \left( -1+z \right) ^{-2}-{\frac {13}{27}}\, \left( -1+z \right)
^{-1}+{\frac {26}{27}}\, \left( 2\,z+1 \right) ^{-1}-1/3\, \left( -1+z \right) ^{-3
}.$$
Now we can read off the coefficients, which are
$$ -\frac{7}{9} (n+1) + \frac{13}{27} + \frac{26}{27} (-2)^n +
\frac{1}{3} \frac{1}{2} (n+1)(n+2)$$
which gives
$$a_n = \frac{26}{27} (-2)^n + \frac{1}{6} n^2 - \frac{5}{18} n + \frac{1}{27}.$$
A: Hint: The general solution of a non-homogenous recurrence relation is equal to the sum of the general solution of a homogenous recurrence relation and a partial solution of a non-homogenous recurrence relation. So you have only to find the last. 
I corrected the rest of the text:
If the right  side of the given equation is a polynomial in $n$ of degree $m$ then  a partial solution can be found in the form $a_n = n^rf(n)$ where $f(n)$ is a  polynomial in $n$ of degree $m$ and $r$ is the multiplicity of the root $1$ of the characteristic equation (in your case $r=1$). Substitute it in your equation and find  $f(n)$.
A: For every $x=(x_n)$, define $L(x)=y$ by $y=(y_n)$ with $y_n=x_{n+2}+x_{n+1}-2x_n$. One knows that $L(u)=L(v)=0$ where $u=(u_n)$, $v=(v_n)$, $u_n=(-2)^n$ and $v_n=1$ for every $n$.
One wants to solve $L(a)=c$ where $c=(c_n)$ and $c_n=n$ for every $n$.  Let $w=(w_n)$ where $w_n=n^2$ for every $n$. Note that $L(c)=3$ and $L(w)=6c+5$.
Thus, $L(3w-5c)=18c$ hence $L(\lambda u+\mu v+\frac16w-\frac5{18}c)=$ $____$ for every scalar $(\lambda,\mu)$. 
Can you finish?
A: 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}$.
