<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] First you find the homogeneous solution : $u_{n+2} - 3u_{n+1} + 2u_n = 0 \to x^2-3x+2 = 0 \to (x-1)(x-2) = 0 \to x = 1, 2 \to u_h = a\cdot 1^n + b\cdot 2^n$, then you find the particular solution $u_p = cn+d$. Thus the general solution is:
$u_n = u_h + u_p = a + b\cdot 2^n + cn + d$. Note that you still have to find $a,b,c,d$, and these values can be determined from $u_0,u_1,u_2,u_3$ which can be determined from the recursive equation.
</s>