Solution of recurrence relation

Question

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

Answer 1

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

Answer 2

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.