Suppose you have a recurrence relation like:

$\displaystyle {x_{n + 2}} - 3{x_{n + 1}} + 2{x_n} = n{\rm$

**(1)**
With $\displaystyle {x_0} = {x_1} = 1$

And you want to find the closed form, of it ( i.e $\displaystyle {x_n}=f(n) $ ).

In the Mathematics for the analysis of Algorithms, by Knuth and Greene it has the following procedure:

We construct a function G(z): $\displaystyle G(z) = \sum\limits_i {{x_i}{z^i}} $

Then we multiply

**(1)** by $\displaystyle {z^{n+2}}$ and sum over all n obtaining:

$\displaystyle \sum\limits_{n \ge 0} {{x_{n + 2}}{z^{n + 2}}} - 3z\sum\limits_{n \ge 0} {{x_{n + 1}}{z^{n + 1}}} + 2{z^2}\sum\limits_{n \ge 0} {{x_n}{z^n}} = \sum\limits_{n \ge 0} {n{z^{n + 2}}} \Rightarrow$

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

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

And now it says that we would like to recover the coefficient of $\displaystyle {z^n}$ in G(z).

**a) **But what does that mean? The only z powers i see in the last equation is $\displaystyle {z}$, $\displaystyle {z^2}$, $\displaystyle {z^3}$. So what coefficient of $\displaystyle {z^n}$ is he talking about?

And then it says that if the denominators of the fractions in G(z) where linear the recovery problem would be simple and that each term would just be a geometric series?

**b) **How come the last one? What exactly does it mean?
And now the most important question, which is about the derivation of the solution.

Book continues saying that since the denominators of the fractions in G(z) are not linear, we express the solution for G(z) in partial fractions so we obtain:

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

**(2)**
And now it says that we should note that the only nonlinear denominators are just higher powers of a linear factor.

So these terms can be expanded by the binomial theorem and then $\displaystyle {x_n}$ can be easily computed to be:

$\displaystyle {x_n} = {2^n} - \frac{{{n^2} + n}}{2}$

**c) **So my question is: How $\displaystyle {x_n}$ can be easily computed from

**(2)**???? I don't get it.

Any help with a), b), c) questions and especially with c)?

Thanks in advance.