Generating functions - deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$

I would like some help with deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ using generating functions.

I have managed to do this for $1^2 + 2^2 + 3^2 +\cdots$ by putting

$$f_0(x) = \frac{1}{1-x} = 1 + x + x^2 + x^3 +\cdots$$

$$f_1(x) = x \frac{d}{dx}[f_0(x)] = \frac{1}{(1-x)^2} = 0 + x + 2x^2 + 3x^3 +\cdots$$ $$f_2(x) = x \frac{d}{dx}[f_1(x)] = \frac{x^2+x}{(1-x)^3} = 0^2 + 1^2x + 2^2x^3 + 3^2x^3+\cdots,$$

and I assume I'm supposed to be able to do something similar in this case, but things get trickier when it's bounded by n and I keep getting stuck.

Solution 1:

Given a generating function $f(x)$ for $a_n$, the generating function for $\sum_{i=0}^n a_i$ is $\sum_{n\geq 0} (\sum_{i=0}^n a_i)x^n = (\sum_{n\geq 0} x^n)(\sum_{n\geq 0} a_nx^n) = \frac{1}{1-x} f(x)$.

In this case, we have $f(x) = \frac{x(1+x)}{(1-x)^3}$ as you mention, so the desired generating function is $\frac{x(1+x)}{(1-x)^4}$. This has a partial fraction expansion:

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

Since $1/(1-x)^{k+1}$ is the generating function for ${n+k}\choose{k}$ (we can see this by repeatedly differentiating $\frac{1}{1-x}$), this gives us:

$$1^2+2^2+\cdots+n^2 = {{n+1}\choose 1} - 3{{n+2}\choose 2} + 2{{n+3}\choose 3} = \frac{n(n+1)(2n+1)}{6}$$

By the way, we can avoid all this work with a good choice of basis. Since $n^2 = {n \choose 0} - 3{{n+1}\choose 1} + 2{{n+2}\choose 2}$, we have:

$$\sum_{i=0}^n i^2 = \sum_{i=0}^n \left({i \choose 0} - 3{{i+1}\choose 1} + 2{{i+2}\choose 2}\right) = {{n+1}\choose 1} - 3{{n+2}\choose 2} + 2{{n+3}\choose 3}$$

All we need here is the sum $\sum_{i=0}^n {{i+k}\choose k} = {{n+k+1}\choose {k+1}}$, which follows from the simple generating functions identity $\frac{1}{(1-x)^k}\cdot \frac{1}{1-x} = \frac{1}{(1-x)^{k+1}}$.

Solution 2:

Brute force:

$$f(x) \triangleq \sum_{r=0}^{n+1}x^r=\frac{x^{n+2}-1}{x-1} $$ $$f'(x) = \sum_{r=0}^{n+1}rx^{r-1} = \sum_{r=0}^{n}(r+1)x^r$$ $$f''(x) = \sum_{r=0}^{n}r(r+1)x^{r-1} \therefore xf''(x)=\sum_{r=0}^{n}r(r+1)x^{r} = \sum_{r=0}^n\left(r^2+r\right)x^r$$ $$f'(x)-(f(x)-x^{n+1}) = \sum_{r=0}^{n}rx^r$$ So $$\sum_{r=1}^nr^2x^r =xf''(x) - (f'(x)-(f(x) - x^{n+1}))$$ Finally take the limit as $x \to 1$, which might get ugly, and Bob's your uncle.

[edit] Changed $$\sum_{r=1}^nr^2x^r =f''(x) - (f'(x)-(f(x) - x^{n+1}))$$ to $$\sum_{r=1}^nr^2x^r =xf''(x) - (f'(x)-(f(x) - x^{n+1}))$$

Solution 3:

Hint: The following perspective with focus on operator methods might also be useful.

We can successively apply the $\left(x\frac{d}{dx}\right)$-operator to a generating function

\begin{align*} A(x)=\sum_{n=0}^{\infty}a_nx^n \end{align*}

to obtain

\begin{align*} \left(x\frac{d}{dx}\right)A(x)&=\sum_{n=0}^{\infty}na_nx^n\\ \left(x\frac{d}{dx}\right)^2A(x)&=\sum_{n=0}^{\infty}n^2a_nx^n \end{align*}

Multiplication of $A(x)$ with $\frac{1}{1-x}$ results in summing up the coefficients $a_n$ \begin{array}{crl} (a_n)_{n\geq 0}\qquad &\qquad A(x)=&\sum_{n=0}^{\infty}a_nx^n\\ \left(\sum_{k=0}^{n}a_k\right)_{n\geq 0}\qquad&\qquad\frac{1}{1-x}A(x)=&\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_k\right)x^n \end{array}

It's also convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series.

Putting all together and applying it to the geometric series $\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n$ we finally obtain

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

Comment:

• In (1) we use the binomial series expansion and $[x^n]x^kA(x)=[x^{n-k}]A(x)$

• In (2) we use $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k=\binom{n+k-1}{n-1}(-1)^k$

Solution 4:

To answer otherwise, you can use the known fact that the sum of the first $n$ positive odd numbers is equal to $n^2$. So you have $$\begin{cases}1=1^2\\1+3=2^2\\1+3+5=3^2\\1+3+5+7=4^2\\................\\1+3+5+…….+(2n-1)=n^2 \end{cases}$$ Therefore $$\sum_{i=1}^{i=n}n^2=n+(n-1)3+(n-2)5+(n-3)7+………+2(2n-3)+(2n-1)$$ That is to say $$\sum_{i=1}^{n}n^2=\sum_{k=0}^{n-1}(n-k)(2k+1)=\frac{n(n+1)(2n+1)}{6}$$ NOTE.- Quite different story is the sequence of the corresponding inverse squares; one has the Euler’s formula $$\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{(\pi)^2}{6}$$