Using Generating Functions to Solve Recursions I have the recursion $A(n) = A(n-1) + n^2 - n$ with initial conditions $A(0) = 1$.  I attempted to solve it using generating functions and I'm not quite sure I have it right, so I thought I might ask if anyone could take a look at my method so far.
First I set up $A(x) = \sum(a(n)x^n)$ and plugged in the definition of $A(n)$ to get $\sum(A(n-1) + n^2 - n)x^n)$ so that $n^2$ and $n$ could be reduced to their closed forms.  
I'm not sure how I should handle the $A(n-1)$ term though without iterating further (perhaps I should?) and I'm starting to wonder if there was a way to produce a generating function for $A(n) - A(n-1)$ so that I could substitute for $n^2 - n$ directly.  Does anyone have any suggestions?
 A: As you wrote
$$
   G(x) = \sum_{n=0}^\infty a_n x^n = x + x \sum_{n=1}^\infty a_n x^{n-1} = x + x \sum_{n=1}^\infty \left(a_{n-1} + n(n-1)\right) x^{n-1} = \\ x + x G(x) + x^2 \sum_{n=2}^\infty n(n-1) x^{n-2} = x + x G(x) + x^2 \frac{d^2}{dx^2} \sum_{n=0}^\infty  x^{n}
$$
Now solve for $G(x)$ and evaluate the remaining sum:
$$
    G(x) = \frac{x \left(1-x +3 x^2-x^3\right)}{(1-x)^4}
$$
Now sure whether this helps finding the closed form for $a_n$.
It is much easier to note that the recurrence reads $a_n - a_{n-1} = n(n-1)$, and thus
$$
   a_n = n (n-1) + a_{n-1} = n(n-1) + (n-1)(n-2) + a_{n-2} = \sum_{k=1}^{n} k(k-1) + a_0
$$
Thus
$$
  a_n = 1 + \frac{1}{3} (n-1) n (n+1)$$
A: Another take, applying the techniques of Wilf's "generatingfunctionology". First write the recurrence as (no, no sign error there):
$$
a_{n + 1} = a_n + n^2 + n \quad a_0 = 1
$$
Define the ordinary generating function:
$$
A(z) = \sum_{n \ge 0} a_n z^n
$$
By the properties of generating functions,
with the operator $D = \dfrac{d}{d z}$ we have:
$$
\frac{A(z) - a_0}{z} = A(z) + ((z D)^2 + z D) \frac{1}{1 - z}
$$
Substituting $a_0$ gives:
$$
A(z) = \frac{1 - 3 z + 5 z^2- z^3}{(1 - z)^4}
$$
In partial fractions:
$$
A(z) = \frac{2}{(1 - z)^4} 
         - \frac{4}{(1 - z)^3} 
         + \frac{2}{(1 - z)^2} 
         + \frac{1}{1 - z}
$$
Expanding by the binomial theorem, with $\binom{-r}{n} = (-1)^n \binom{r + n - 1}{n - 1}$:
$$
\begin{align*}
a_n &= 2 \binom{n + 3}{3} - 4 \binom{n + 2}{2} + 2 \binom{n + 1}{1} + 1 \\
    &= \frac{n^2 - n + 3}{3}
\end{align*}
$$
