Sum of squares using generating functions

Question

I tried using generating functions to solve the sum of squares formula based on the recurrence $a_n = a_{n-1} + n^2$ with $a_0 = 0$.

$$G(x) = \sum_{n=0}^{\infty} a_n x^n \\ G(x) - 0 = \sum_{n=1}^{\infty} (a_{n-1} + n^2) x^n \\ G(x) = \sum_{n=1}^{\infty} a_{n-1}x^n + \sum_{n=1}^{\infty} n^2 x^n \\ G(x) = x\sum_{n=0}^{\infty} a_{n}x^n + (-0^2x^0 + \sum_{n=0}^{\infty} n^2 x^n) \\ G(x) = xG(x) + \sum_{n=0}^{\infty} n^2 x^n \\ G(x) = xG(x) + \frac{x(x+1)}{(1-x)^3} \\ G(x) = \frac{x(x+1)}{(1-x)^4} \\ G(x) = \frac{0}{(1-x)^1} + \frac{1}{(1-x)^2} - \frac{3}{(1-x)^3} + \frac{2}{(1-x)^4} \\ G(x) = \frac{1}{(1-x)^2} - 3\frac{1}{(1-x)^3} + 2\frac{1}{(1-x)^4} $$

Once I get to a spot like this I am unsure how to proceed. What is the smart way to solve the rest of this if you haven't seen a particular type of generating function before?

Answer 1

It is convenient to obtain the coefficients already from \begin{align*} G(x)=\frac{x(x+1)}{(1-x)^4} \end{align*}

Using the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series we get

\begin{align*} [x^n]G(x)&=[x^n]\frac{x(x+1)}{(1-x)^4}\\ &=[x^n]x(x+1)\sum_{n=0}^{\infty}\binom{-4}{n}(-x)^n\tag{1}\\ &=\left([x^{n-2}]+[x^{n-1}]\right)\sum_{n=0}^{\infty}\binom{n+3}{3}x^n\tag{2}\\ &=\binom{n+1}{3}+\binom{n+2}{3}\\ &=\frac{1}{6}(n+1)n(n-1)+\frac{1}{6}(n+2)(n+1)n\\ &=\frac{1}{6}n(n+1)(2n+1) \end{align*}

Comment:

• In (1) we use the binomial series representation

• In (2) we use the linearity of the coefficient of operator and $[x^n]x^kG(x)=[x^{n-k}]G(x)$. We also use the binomial formula $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k=\binom{n+k-1}{n-1}(-1)^k$

Since \begin{align*} G(x)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}k^2\right)x^n \end{align*}

we conclude \begin{align*} \sum_{k=0}^{n}k^2=\frac{1}{6}n(n+1)(2n+1)\qquad\qquad n\geq 0 \end{align*}

Hint: You might also be interested in an operator based approach.