<s>[INST] Solution of recurrence relation I want to find a solution of $$ u(n+2) - 3u(n+1)+2u(n) = n, \text{ for } n \ge 0, u(1)=u(0)=1$$
Update: 
Solution using Joel idea:
1) multiply by $x^n$: $$\frac{1}{x^2}u(n+2)x^{n+2}-\frac{1}{x}3u(n+1)x^{n+1}+2u(n)x^n=nx^n$$
2) sum from n=0 to inf: $$\frac{1}{x^2}\sum_{n \ge 2}u(n)x^{n}-\frac{3}{x}\sum_{n \ge 1}u(n)x^{n}+2\sum_{n \ge 0}u(n)x^n=\sum_{n \ge 0}nx^n$$
3) Let $\sum_{n \ge 0}u(n)x^n=G(x)$. Then $\sum_{n \ge 2}u(n)x^{n} = G(x)-1-x$. $\sum_{n \ge 1}u(n)x^{n} = G(x)-1$, so:
 $$\frac{1}{x^2}(G(x) - 1 - x)-\frac{3}{x}(G(x)-1)+2G(x)=\frac{x}{(1-x)^2}$$
 $$G(x) = \frac{1-2x+\frac{x^3}{(x-1)^2}}{1-3x+2x^2} = \frac{1}{(x-1)^2}+\frac{1}{(x-1)^3} + \frac{1}{1-2x}$$
4) $G(x)=\sum_{n \ge 0}u(n)x^n=\sum_{n \ge 0} (1+n)x^n - \frac{1}{2} \sum_{n \ge 0} (1+n)(n+2)x^n+\sum_{n \ge 0}(2x)^n$
5) So the answer is: $u(n)=2^n-\frac{1}{2}n(n+1)$
Thank you, Joel
 [/INST] If we let $G(x) = \sum_{n=0}^\infty u(n) x^n$, then $$G(x)-3xG(x)+2x^2G(x)=1-2x+\sum_{n=2}^\infty nx^n$$
Recall that $\sum_{n=1}^\infty nx^{n-1} = (1-x)^{-2}$, and so $$(1-3x+2x^2)G(x)=1-2x+x((1-x)^{-2}-1)$$
Thus $$G(x) = \frac{1-x}{1-3x+2x^2} + \frac{x}{(1-x)^2(1-3x+2x^2)}.$$
We can factor $1-3x+2x^2 = (x-1)(2x-1)$. And so:
$$G(x) = \frac{-1}{(2x-1)} + \frac{x}{(x-1)^3(2x-1)}$$
From here use a partial fraction decomposition to determine the explit form of $u(n)$.
</s>