Hi I'm studying for my finals and having trouble with this question:

Consider the following recurrence relation:

$\displaystyle a_{n+2} = a_{n+1} + a_{n} + n$ for $\displaystyle n\geqslant 0$ where $\displaystyle a_{0} = a_{1} = 1$.

Write the corresponding generating function in its closed form.

I've set up the generating function as

$\displaystyle G(z) = a_{0} + a_{1}z + a_{2}z^{2} + a_{3}z^{3} + a_{4}z^{4} + ...$ and I've gotten as far in my working as:

$\displaystyle G(z)(1-z-z^{2})= 1 + nz^{2}(1 + nz + nz^{2} + ...)$

But according to the solutions I should at this stage be getting:

$\displaystyle G(z)(1-z-z^{2})= 1 + z^{3}(1 + 2z + 3z^{2} + ...)$

What am I doing wrong?

I'd really appreciate some help on this one, thanks in advance!

Cheers,

Roro