Solve $a_{n+1} - a_n = n^2$ using generating functions The Full Question
Using the method of generating functions, solve $a_{n+1} - a_n = n^2$ where $a_0 = 1$
My Research
Scanned the website for similar answers, reviewed the following links:
Solve the following recurrences using generating functions.
can we use generating functions to solve the recurrence relation $a_n = a_{n-1} + a_{n-2}$, $a_1=1$, $a_2=2$?
Solving a recurrence equation using generating functions
Using Generating Functions to Solve Recursions
Solve the following recursive relation by using generating functions
Solve a recursion using generating functions?
Solving recurrences using generating functions
None of them would make my question a duplicate and none of them really addressed what I was having difficulty with.
My Work
If we multiply each side by $x^{n+1}$ and sum each of the possible cases $a_0,a_1,\dots$
we have:
$$\sum\limits_{j=0}^{\infty}{a_{n+1}x^{n+1}} - x\sum\limits_{j=0}^{\infty}a_nx^n = \sum\limits_{j=0}^{\infty}n^2x^{n+1}$$
If we let $f(x) = \sum\limits_{j=0}^{\infty}a_nx^n$ our equation transforms into:
$$f(x)-a_0 -xf(x) = \sum\limits_{j=0}^{\infty}n^2x^{n+1}$$
Factoring $f(x)$ and observing the LHS is a well known generating functions and using the fact that $a_0 = 1$, we get:
$$f(x)(1-x) = \frac{x(1+x)}{(1-x)^3} + 1 \implies f(x) = \frac{x(1+x)}{(1-x)^4} + \frac{1}{1-x}$$
We now need the coefficients of $x^n$ of these two functions we are adding. The right function it is well known that is has coefficients of $1$. We need partial fraction decomposition to obtain the coefficients of the left hand side.
$$\frac{x(1+x)}{(1-x)^4}= \frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}+\frac{D}{(1-x)^4}$$
$\implies x(1+x)= A(1-x)^3+B(1-x)^2+C(1-x)+D$
Expanding this, we have
$Ax^3+3Ax^2 - 3Ax + A + Bx^2 -2Bx + B +C -Cx +D$
Which gives us the system of equations:
1) $A+B+C+D = 0$
2) $-3A-2B-C =1$
3) $3A+B = 1$
4) $A = 0$
5) $D = 0$
$3(0)+B=1 \implies B=1$ Using equations 3&4
$-3(0) -2 - C=1\implies C=3$ Using equations Using equations 2&1 and the result above
$0+1+3+0 = 0$  plugging in our results to equation 1
that is obviously not correct. Where did I make my mistake. I feel I'm very close and must have messed up the partial fraction decomposition somewhere, but maybe the mistake is somewhere else. Can anyone find where I went wrong?
 A: You made a mistake in solving 
$$ x(1+x)= A(1-x)^3+B(1-x)^2+C(1-x)+D$$
A faster way to solve this is the following:
$$x = 1 \Rightarrow D=2$$
Next derivate 
$$1+2x=-3A(1-x)^2-2B(1-x)-C$$
plug in $x=1$. Then derivate again, and plug in $x=1$. Continue...
A: Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$. Take the recurrence, multiply by $z^n$, sum over $n \ge 0$:
$$
\sum_{n \ge 0} a_{n + 1} z^n - \sum_{n \ge 0} a_n z^n = \sum_{n \ge 0} n^2 z^n
$$
Recognize some sums, note that:
$\begin{align}
\sum_{n \ge 0} z^n
  &= \frac{1}{1 - z} \\
\sum_{n \ge 0} n z^n
  &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\
  &= \frac{z}{(1 - z)^2} \\
\sum_{n \ge 0} n^2 z^n
  &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{z}{(1 - z)^2} \\
  &= \frac{z + z^2}{(1 - z)^3} \\
\end{align}$
$$
\frac{A(z) - a_0}{z} - A(z) = \frac{z + z^2}{(1 - z)^3}
$$
Plug in $a_0 = 1$, solve for $A(z)$, split into partial fractions:
$\begin{align}
A(z)
  &= \frac{1 - 3 z + 4 z^2}{1 - 4 z + 6 z^2 - 4 z^3 + z^4} \\
  &= \frac{4}{(1 - z)^2}
       + \frac{5}{(1 - z)^3}
       + \frac{2}{(1 - z)^4}
\end{align}$
Consider that:
$$
(1 - z)^{-r}
  = \sum_{n \ge 0} (-1)^n \binom{-r}{n} z^n
  = \sum_{n \ge 0} \binom{r + n - 1}{r - 1} z^n
$$
Note that $\binom{n + r - 1}{r - 1}$ is a polynomial of degree $r - 1$ in $n$.
Pick the coefficient of $z^n$ of $A(z)$:
$\begin{align}
a_n
  &= 4 \binom{n + 1}{1} + 5 \binom{n + 2}{2} + 2 \binom{n + 3}{3} \\
  &= \frac{2 n^3 + 27 n^2 + 91 n + 66}{6}
\end{align}$
