# Finding the sum of first $N$ squares with generating functions

I'm trying to prove the well-known result $$\sum_1^Nn^2=\frac{N(N+1)(2N+1)}6$$ using generating functions. The obvious choice is to set $$f(x)=\sum_{n=1}^N n^2x^n$$, so that we have $$f(x)=(xD)^2\sum_1^N 1x^n=(xD)^2\left(\frac{x^{N+1}-1}{x-1}\right).$$ It seems like it should be easy to find $$f(x)$$, then setting $$x=1$$ to find $$f(1)$$ should be a slam-dunk. Indeed, the text I'm referring to says that direct evaluation is the way and that "after doing two differentiations and a lot of algebra the answer emerges". Somehow, I can't do this. In particular, I get that $$f(x)=\frac{xp(x)}{(x-1)^3},$$ where $$p$$ is a polynomial of degree $$n$$, and the $$(x-1)$$s at the denominator does not cancel with anything in the numerator. I'm puzzled how I'm now supposed to substitute $$x=1$$, since we end up dividing by zero. Can someone help?

• What does the $(xD)^2$ notation mean? – TomGrubb Mar 6 at 7:13
• @TomGrubb $D$ is the differentiation operator (understood to be with respect to $x$). The equation says that $f(x)$ is the result of differentiating the sum, multiplying by $x$, differentiating again and multiplying again. – FredH Mar 6 at 7:32
• @FredH indeed, that's what I meant by $xD$. – YiFan Mar 6 at 8:09

## 2 Answers

\begin{align} f(x) &=(xD)^2\left(\frac{x^{N+1}-1}{x-1}\right)\\ &=(xD)(xD)\left(\frac{x^{N+1}-1}{x-1}\right)\\ &=x\left(xD\left(\frac{x^{N+1}-1}{x-1}\right)+D^2\left(\frac{x^{N+1}-1}{x-1}\right)\right)\\ &=x^2D\left(\frac{x^{N+1}-1}{x-1}\right)+xD^2\left(\frac{x^{N+1}-1}{x-1}\right) \end{align} If $$t=x-1$$: \begin{align} \frac{x^{N+1}-1}{x-1} &=\frac{(t+1)^{N+1}-1}t\\ &=\sum_{k=1}^{N+1}\binom{N+1}kt^{k-1} \end{align} hence \begin{align} &\lim_{x\to 1}D\left(\frac{x^{N+1}-1}{x-1}\right)=\binom{N+1}2& &\lim_{x\to 1}D^2\left(\frac{x^{N+1}-1}{x-1}\right)=2\binom{N+1}3& \end{align} thus \begin{align} \lim_{x\to 1}f(x) &=\binom{N+1}2+2\binom{N+1}3\\ &=\frac{(N+1)N}2+\frac{(N+1)N(N-1)}3\\ &=\frac{3(N+1)N+2(N+1)N(N-1)}6\\ &=\frac{(N+1)N(2N+1)}6 \end{align}

Just apply L'Hopital's rule 3 times to resolve your singularity. I will not write out the details in full $$f(1) = \lim_{x \to 1}\frac{xp(x)}{(x-1)^3} = \frac{(D)^3(xp(x))} {6}$$ where $$D$$ is the differential operator in your notation.