Use generating functions to solve nonhomogeneous recurrence relation

Question

The recurrence relation is

$$a_n = a_{n-1} + a_{n-2} + n,\quad n\ge 2$$

with initial conditions $a_0 = 0$ and $a_1 = 1$.

I know I need to convert the recurrence into series and I have broken it down, but am struggling with getting it into a proper form to do partial fractions.

I have:

$$f(x) = a_0 + a_1x + x\sum_{n\ge 2} a_{n-1}x^{n-1} + x^2\sum_{n\ge 2} a_{n-2}x^{n-2} + \frac{1}{(1-x)^2}$$

Any insight/help is much appreciated!

Answer 1

Write $F(x)$ as the generating function, then

$$F(x)-x-0= (x+x^2)F(x)+x\left({1\over (1-x)^2}-1\right).$$

Solving gives:

$$F(x) = {x\over (1-x-x^2)(1-x)^2}$$

Answer 2

Just manipulate the generating function; \begin{align} f(x)=x+\sum_{n=2}^\infty a_nx^n=&x+x\sum_{n=2}^\infty a_{n-1}x^{n-1}+x^2\sum_{n=2}^\infty a_{n-2}x^{n-2}+x\sum_{n=2}^\infty nx^{n-1}\\ =&x+xf(x)+x^2f(x)+x\,\frac{d}{dx}\sum_{n=2}^\infty x^{n}\\ =&x+xf(x)+x^2f(x)+x\,\frac{d}{dx}\underbrace{\left(\frac{1}{1-x}-x-1\right)}_{x^2/(1-x)}\\ =&x+xf(x)+x^2f(x)+x\,\frac{2x-x^2}{(1-x)^2}, \end{align}

and now solve for $f(x)$.