This article uses Project Euler Problem #6 as an excuse to ramble on about generating functions.
The entirety of this article was informed by Herbert Wilf’s awesome book, Generatingfunctionology [1]; more specifically, informed by \(\S 2.2\): The Calculus of Formal Ordinary Power Series Generating Functions.
This article should be accessible to those comfortable with arithmetic, elementary algebra, and elementary differential calculus.
The problem
The sum of the squares of the first ten natural numbers is,
\[1^2 + 2^2 + ... + 10^2 = 385.\]The square of the sum of the first ten natural numbers is,
\[(1 + 2 + ... + 10)^2 = 55^2 = 3025.\]Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is \(3025 - 385 = 2640\).
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
- Project Euler Problem #6: Sum Square Difference [2].
Finding the solution
Some comments on time and space complexity: The brute force approach, looping and accumulating, is of \(O(n)\) time and \(O(1)\) space complexity. Assuming fixed width integers, i.e. not arbitrary-precision integers, a closed form solution is of \(O(1)\) time and space complexity. If the integers go beyond the typical register size, the arithmetic cost grows with \(n\), but I am not certain of the asymptotic complexity. .
There are a couple ways to solve this one: brute force, or some formulas. To make this writeup distinct from most others on Problem #6, we will derive the formulas ourselves with generating functions.
Geometric series
As our foundation, we have the geometric series \[ \sum_{n\ge 0} x^n = \frac{1}{1-x}. \tag{1}\]
We can make some sense of this with some good ol’ distribution: \[ \begin{aligned} (1-x)\cdot \sum_{n\ge 0}x^n &= \sum_{n\ge 0}x^n - \sum_{n\ge 0}x^{n+1} \\ &=(1+x+x^2+x^3+\cdots)-(x+x^2+x^3+\cdots)\\ &=1 \end{aligned} \]
We can also bring in some heavier machinery.
Definition 1 The Cauchy product of two series \(a_n\) and \(b_n\): \[ \sum_n a_n x^n \sum_n b_n x^n = \sum_n c_n x^n,\quad c_n=\sum_k a_k b_{n-k}. \]
Taking the expression \((1-x)\) to be the infinite series \(\left(1-x+0x^2+0x^3+0x^4\cdots\right)\), we can apply Definition 1 to the product \((1-x)\cdot \sum_{n\ge 0}x^n\): \[ \begin{aligned} (1-x)(1+x+x^2+x^3+x^4+\cdots) &=x^0(1\cdot 1)\\ &\quad +x^1 (1\cdot 1 + -1\cdot 1)\\ &\quad + x^2 (1\cdot 1 + -1\cdot 1 + 0\cdot 1) \\ &\quad + x^3 (1\cdot 1 + -1\cdot 1 + 0\cdot 1 + 0\cdot 1)\\ &\quad + x^4 (1\cdot 1 + -1\cdot 1 + 0\cdot 1 + 0\cdot 1 + 0\cdot 1)+\cdots \\ &= x^0 + x^1 \cdot 0 + x^2 \cdot 0 + x^3 \cdot 0 + x^4 \cdot 0+\cdots \\ &= 1. \end{aligned} \]
Pretty cool! Either way you look at it—with the Cauchy product or with the distributive property of multiplication—Equation 1 seems to make sense.
Encoding the sequence of natural numbers
The series \(\sum_{n\ge 0}x^n\) encodes the sequence \(\{1,1,1,\dots\}\). That is, the coefficient of every term in the series is \(1\). The first step toward our solution is to build from this to find a series that encodes the sequence of natural numbers \(\{n\}_{n\ge 0}=\{0,1,2,3,\dots\}\). We can do this with calculus: \[ D\left[\sum_{n\ge 0}x^n\right]=\sum_{n\ge 0}n x^{n-1}. \]
Expanding the first handful of terms, we see \[ 0+1+2x+3x^2+4x^3+\cdots nx^{n-1}+\cdots. \] It will be more convenient for each term’s coefficient to match its degree; to do that, we’ll multiply the whole series by \(x\). Here, we’ll borrow Herbert Wilf’s notation, and define the operator \(xD\) to mean: take the derivative of (with respect to x) then multiply by x. \[ \begin{aligned} (xD)\left[\sum_{n\ge 0}x^n\right]&=x\sum_{n\ge 0}n x^{n-1}\\ &= \sum_{n\ge 0}n x^{n}\\ &=0+x+2x^2+3x^3+\cdots \end{aligned} \] So the generating function for the sequence of natural numbers is \[ \begin{aligned} (xD)\left[\sum_{n\ge 0}x^n\right]&=(xD)\left[\frac{1}{1-x}\right]\\ &=\frac{x}{(1-x)^2}. \end{aligned} \] The result is summarized here for reference: \[ \sum_{n\ge 0}n x^{n} = \frac{x}{(1-x)^2}. \tag{2}\] Now we try for the sequence of squares.
Encoding the sequence of squares
To find a generating function for the sequence of squares, we can build from the sequence of natural numbers. Again, the tool we need is found in calculus: \[ \begin{aligned} (xD)\left[\sum_{n\ge 0}nx^n\right]&=\sum_{n\ge 0}n^2x^n\\ &=0+x+4x^2+9x^3+16x^4+\cdots \end{aligned} \] So the generating function for the sequence of squares is \[ \begin{aligned} (xD)\left[\sum_{n\ge 0}nx^n\right]&=(xD)\left[\frac{x}{(1-x)^2}\right]\\\\ &=x\left(\frac{1}{(1-x)^2}+x\frac{2}{(1-x)^3}\right) \\\\ &=\frac{x+x^2}{(1-x)^3}. \end{aligned} \] The result is summarized here for reference: \[ \sum_{n\ge 0}n^2x^n=\frac{x+x^2}{(1-x)^3}. \tag{3}\] We have found generating functions for the sequence of natural numbers and the sequence of squares. Now all that’s left to do is some summing.
Partial sum of a sequence
The previous two sections may have seemed a bit aimless: yes, we know that the \(n^{\text{th}}\) natural number is \(n\); we know that the square of the \(n^{\text{th}}\) integer is \(n^2\). What are the generating functions for? The utility of these generating functions is to encode the sequences into algebraic objects which are more easily manipulated than the sequences themselves. One such manipulation yields the partial sum of a sequence, which is exactly what we need:
Proposition 1 A restatement of Rule \(5\) in \(\S 2.2\) of Generatingfunctionology. If \[ f(x)=\sum_{n\ge 0}a_n x^n, \] then \[ \frac{f(x)}{(1-x)}=\sum_{n\ge 0} \left(\sum_{j=0}^{n} a_j\right) x^n. \]
That is, \(\frac{f(x)}{(1-x)}\) gives us the sequence of partial sums of the sequence encoded by \(f(x)\).
Remembering the identity in Equation 1, we can apply Definition 1 to see if Proposition 1 makes any sense: \[ \begin{aligned} \frac{f(x)}{(1-x)}&=(a_0+a_1x+a_2x^2+a_3x^3+\cdots)(1+x+x^2+x^3+\cdots)\\ &= a_0 +x(a_0+a_1) +x^2(a_0+a_1+a_2) +x^3(a_0+a_1+a_2+a_3) + \cdots \end{aligned} \] Seems to make sense. With this tool, we have everything we need to solve the problem.
Square of the sum
To find a closed form for the sum of the first \(n\) natural numbers, we apply Proposition 1 to Equation 2, then apply coefficient extraction:
\[ \begin{aligned} {[x^n]}\frac{x}{(1-x)^3}&=\binom{n+1}{2}\\\\ &=\frac{(n+1)!}{2!(n+1-2)!}\\\\ &=\frac{(n+1)(n)(n-1)\cdots 2}{2(n-1)(n-2)\cdots 2}\\\\ &=\frac{n(n+1)}{2}. \end{aligned} \]
\({[x^n]}f(x)\) means: the coefficient of the \(x^n\) term in the series \(f(x)\). For example, \([x^k]\left(\sum_{n\ge 0}n^2x^n\right)=k^2.\)
For clarification on coefficient extraction from functions of this form, see Equation 1.5.5 in the Second Edition of Generatingfunctionology [1].
We are looking for the square of the sum, not just the sum, of the first \(n\) natural numbers, so we have \[ \sum_{n\ge 0} \left(\sum_{j=0}^{n} j \right)^2 x^n = \sum_{n\ge 0} \left(\frac{n(n+1)}{2}\right)^2 x^n. \tag{4}\]
Sum of the squares
To find a closed form for the sum of the first \(n\) squares, we apply Proposition 1 to Equation 3, then apply coefficient extraction to the resulting expression: \[ \begin{aligned} {[x^n]}\frac{x+x^2}{(1-x)^4} &= [x^n]\frac{x}{(1-x)^4} + [x^n]\frac{x^2}{(1-x)^4} \\\\ &=\binom{n+2}{3} + \binom{n+1}{3} \\\\ &=\frac{(n+2)!}{3!(n+2-3)!}+\frac{(n+1)!}{3!(n+1-3)!}\\\\ &=\frac{(n+2)(n+1)(n)(n-1)\cdots 2}{3!(n-1)(n-2)\cdots 2} + \frac{(n+1)(n)(n-1)(n-2)\cdots 2}{3!(n-2)(n-3)\cdots 2}\\\\ &=\frac{(n+2)(n+1)(n)}{6} + \frac{(n+1)(n)(n-1)}{6}\\\\ &=\frac{(n+1)(n)\left[n+2+n-1\right]}{6}\\\\ &=\frac{n(n+1)(2n+1)}{6}. \end{aligned} \] And so, we have \[ \sum_{n\ge 0} \left(\sum_{j=0}^{n} j^2\right) x^n = \sum_{n\ge 0} \frac{n(n+1)(2n+1)}{6} x^n. \tag{5}\]
The solution
Now that we have closed forms for the square of the sum of the first \(n\) natural numbers (Equation 4) and the sum of the first \(n\) squares (Equation 5), a solution is readily available: \[ \left(\frac{n(n+1)}{2}\right)^{2} - \frac{n(n+1)(2n+1)}{6}, \] which simplifies nicely to \[ \frac{1}{12} (n-1) (n) (n+1) (3 n+2). \tag{6}\]