Solving recurrence by generating function Notice: This is an ungraded practice problem. My solution is correct.
Question: How can I solve the problem below using generating functions which make it clear it uses the sum of squares forumla?
Problem: Solve $a_{n+1} - a_n = n^2$, $n \ge 0$, $a_0 = 1$ by the method of generating functions.
My solution:
$$
\begin{array}{r c l}
a_{n+1} - a_n & = & n^2 \\
a_{n+1} x^{n+1} - x a_n x^n & = & n^2x^{n+1} \\
\sum_{i = 0}^{\infty}a_{i+1} x^{i+1} - \sum_{i = 0}^{\infty}a_{i+1} x a_i x^i & = & \sum_{i = 0}^{\infty} i^2 x^{i+1} \\
\end{array}
$$
$$\text{Let } f(x) = \sum_{i = 0}^{\infty}a_i x^i \text{. Then:}$$
$$
\begin{array}{r c l l}
(f(x) - a_0) - xf(x) & = & \sum_{i = 0}^\infty i^2 x^{i+1} \\
f(x) & = & \frac{1}{1-x} (a_0 + \sum_{i = 0}^\infty i^2 x^{i+1}) \\
 & = & (1 + x + x^2 + ...) (1 + x^2 + 4x^3 + 9x^4 + ...) \\
 & = & 1 + x + 2x^2 +6x^3 + ... & \text{expansion by hand}
\end{array}
$$
What routes can I take that make it clear that the last line is equivalent to $\sum_{i = 0}^\infty 1 + \frac{i(i-1)(2i-1)}{6}$? It must be done using generating functions.


We obtain
  \begin{align*}
\color{blue}{f(x)}&=\frac{1}{1-x}\left(a_0+\sum_{i=0}^\infty  i^2x^{i+1}\right)\\
&=\frac{1}{1-x}\left(1+x\sum_{i=0}^\infty i^2 x^i\right)\\
&=\frac{1}{1-x}+x\left(\sum_{j=0}^\infty x^j\right)\left(\sum_{i=0}^\infty i^2x^i\right)\\
&=\frac{1}{1-x}+x\sum_{n=0}^\infty\left(\sum_{{i+j=n}\atop{i,j\geq 0}}i^2\right)x^n\tag{1}\\
&=\frac{1}{1-x}+x\sum_{n=0}^\infty\left(\sum_{i=0}^n i^2\right)x^n\\
&=\frac{1}{1-x}+\sum_{n=0}^\infty\frac{n(n+1)(2n+1)}{6}x^{n+1}\\
&=\sum_{n=0}^\infty x^n+\frac{1}{6}\sum_{n=1}^\infty(n-1)n(2n-1)x^n\\
&\,\,\color{blue}{=\sum_{n=0}^\infty\left(1+\frac{1}{6}(n-1)n(2n-1)\right)x^n}
\end{align*}
The essence is applying the Cauchy product formula in (1): Multiplication of $\sum_{i=0}^\infty c_i x^i$ with $\frac{1}{1-x}$ transforms the coefficient $c_i \to \sum_{i=0}^n c_i$, here with $c_i=i^2$.

