Solving recurrence by generating function

Question

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.

Answer 1

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$.