Sum of squares using generating functions 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?
 A: 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.
