# 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$$.
• I didn't know I could go from $$\sum_{i=0}^\infty i^2 x^i$$ to $$\sum_{i=0}^\infty\frac{i(i+1)(2i+1)}{6}x^i$$ That must be what I was missing (I haven't seen the in-between steps you have posted before). – wybkqqnob Oct 21 '18 at 22:56