Finding the generating function of $\sum_{k=1}^n k^2$

Question

I am new to generating function and I am stuck with this problem, any suggestion on how to solve it. Thank you

Answer 1

Rearrange the terms of the generating function

$$G(x)=1x+(1+4)x^2+(1+4+9)x^3+(1+4+9+16)x^4+\cdots$$

in this way :

$$\begin{array}{ccccc|r} &&&&&\text{sum of lines}\\ \hline 1x&1x^2&1x^3&1x^4&\cdots&x\dfrac{1}{1-x}\\ &4x^2&4x^3&4x^4&\cdots&4x^2\dfrac{1}{1-x}\\ &&9x^3&9x^4&\cdots&9x^3\dfrac{1}{1-x}\\ &&&16x^4&\cdots&16x^4\dfrac{1}{1-x} \end{array}$$

(the sum of lines are consequence of the famous formula for the sum of a geometric series).

Summing the last column, we get

$$G(x)=\underbrace{(x+4x^2+9x^3+16x^4+\cdots)}_{\gamma(x)}\dfrac{1}{1-x}$$

The first factor, $\gamma(x)$, is the generating function of the squares of integers, simpler to be analyzed.

You will find how one can obtain a closed form formula for $\gamma(x)$ at the end of paragraph 2.4 page 5 of this excellent MIT document how to obtain a compact form for $\gamma(x)$.

For more information about the sequence of so-called pyramidal numbers, see here.

Answer 2

\begin{align} \sum_{n\ge 0} \sum_{k=1}^n k^2 z^n &= \sum_{k\ge 1} k^2 \sum_{n=k}^\infty z^n \\ &= \sum_{k\ge 1} k^2 \frac{z^k}{1-z} \\ &= \frac{1}{1-z} \sum_{k\ge 1} k^2 z^k \\ &= \frac{1}{1-z} \sum_{k\ge 1} (k(k-1)+k) z^k \\ &= \frac{1}{1-z} \left(z^2 \sum_{k\ge 1} k(k-1) z^{k-2} + z \sum_{k\ge 1} k z^{k-1}\right) \\ &= \frac{1}{1-z} \left(z^2 \frac{d^2}{dz^2}\sum_{k\ge 1} z^k + z \frac{d}{dz}\sum_{k\ge 1} z^k\right) \\ &= \frac{1}{1-z} \left(z^2 \frac{d^2}{dz^2}\frac{z}{1-z} + z \frac{d}{dz}\frac{z}{1-z}\right) \\ &= \frac{1}{1-z} \left(z^2 \frac{2}{(1-z)^3} + z \frac{1}{(1-z)^2}\right) \\ &= \frac{z(1+z)}{(1-z)^4} \end{align}