Find a generating function for $\sum_{k=0}^{n} k^2$

Question

Find a generating function for $\sum_{k=0}^{n} k^2$

I know my solution is wrong, but why?

My solution:
If $F(x)$ generates $\sum_{k=0}^{n} k^2$ then $F(x)(1-x)$ generates $k^2$.

$\frac{x}{(1-x)^4}: \left\{ 0,1,4,9,16,25... \right\}$
$\frac{x}{(1-x)^3}: \left\{ 0,1,3,5,7,9... \right\}$
$\frac{x}{(1-x)^2}: \left\{ 0,1,2,2,2,2... \right\}$
$\frac{x}{1-x}: \left\{ 0,1,1,1,1,1... \right\}$
$x: \left\{ 0,1,0,0,0,0... \right\}$

So, $F(x)=\frac{x}{(1-x)^5}$ generates $\sum_{k=0}^{n} k^2$

Answer 1

The differences of $\{0,1,2,2,2,2,\dots\}$ are $\{0,1,1,0,0,\dotsc\}$, not $\{0,1,1,1,1,\dotsc\}$.

So you should get

$$\begin{align} x+x^2 &: \{0,1,1,0,0,\dotsc\}\\ \frac{x+x^2}{1-x} &: \{ 0,1,2,2,2,\dotsc\}\\ \frac{x+x^2}{(1-x)^2} &: \{ 0,1,3,5,7,\dotsc\}\\ \frac{x(1+x)}{(1-x)^3} &: \{ 0,1,4,9,\dotsc\} \end{align}$$

and

$$\frac{x(1+x)}{(1-x)^4}$$

as the generating function of $\sum k^2$.

Answer 2

Try to use a cubic polynomial of the general form $an^3+bn^2+cn+d$. You can solve for the coefficients by plugging in a couple different values of n. Then solve the system of equations! A matrix would work nicely. This is really a brute force type thing. I can write up a more elegant solution if you like.

Answer 3

According to the example, how to get the generating function for squares you can do the following:

Use $$ \sum_{n=0}^{\infty}\binom{n+k}k x^n= \frac{1}{(1-x)^{k+1}} $$ and set $$ a\binom{n+3}{3}+ b\binom{n+2}{2}+c\binom{n+1}{1}+d=\frac{n^3}{3}+\frac{n^2}{2}+\frac n2=\sum_{k=1}^n k^2 $$ You'll find $a=2,b=-3,c=1$ and $d=0$. So $$ \frac{2}{(1-x)^4}-\frac{3}{(1-x)^3}+\frac{1}{(1-x)^2} $$ is the generating function, which sums up to Daniel's answer...

Answer 4

Just consider: \begin{align} \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n^2 z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \left( z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \right) \\ &= \frac{z + z^2}{(1 - z)^3} \\ \sum_{n \ge 0} \left( \sum_{0 \le k \le n} k^2 \right) z^n &= \frac{z + z^2}{(1 - z)^4} \end{align} Just for the heck of it: \begin{align} \sum_{0 \le k \le n} k^2 &= [z^n] \frac{z + z^2}{(1 - z)^4} \\ &= [z^{n - 1}] (1 - z)^{-4} + [z^{n - 2}] (1 - z)^{-4} \\ &= (-1)^{n - 1} \binom{-4}{n - 1} + (-1)^{n - 2} \binom{-4}{n - 2} \\ &= \binom{n - 1 + 4 - 1}{4 - 1} + \binom{n - 2 + 4 - 1}{4 - 1} \\ &= \binom{n + 2}{3} + \binom{n + 1}{3} \\ &= \frac{(n + 2) (n + 1) n + (n + 1) n (n - 1)}{3!} \\ &= \frac{(2 n + 1) (n + 1) n}{6} \end{align}