[Click here for a PDF version of this post]

Motivation.

I showed Karl Gauss’s trick for summing a \( 1, 2, \cdots, n \) sequence. Add it up twice, reversing the sum and adding by columns
\begin{equation}\label{eqn:sumOfSquares:21}
\begin{array}{c|c|c|c|c}
1 & 2 & \cdots & n-1 & n \\
n & n-1 & \cdots & 2 & 1
\end{array}
\end{equation}
We get \( n + 1 \), \( n \) times, so
\begin{equation}\label{eqn:sumOfSquares:41}
\sum_{k = 1}^n k = \frac{n}{2}\lr{ n + 1 }.
\end{equation}

Karl pointed out to me that he’d looked up the formula for the sum of squares, and found
\begin{equation}\label{eqn:sumOfSquares:61}
\sum_{k = 1}^n k^2 = \frac{n}{6}\lr{ 2 n + 1 }\lr{ n + 1 }.
\end{equation}

I couldn’t think of some equivalent of the Guassian trick to sum that, but had the vague memory that we could figure it out using difference calculus. I have a little Dover book [1] on the subject that I read some of when I was in school. Without resorting to that book, I tried to dredge up the memory of how this result could be derived.

Difference operator.

The key is defining a difference operator, akin to a derivative

Definition 1.1: Difference operator (reverse.)

It’s also possible to define forward difference operators \( \Delta y_n = y_{n+1} – y_n \), or both, and it turns out that the text uses forward differences. I’ll use reverse difference operator here, since that’s what I tried. The ideas should hold either way.

We can apply the difference operator to some simple sequences, such as \( y_n = \textrm{constant}, y_n = n, y_n = n^2, \cdots \). For those, we find
\begin{equation}\label{eqn:sumOfSquares:81}
\begin{aligned}
\Delta 1
&= 0 \\
\Delta n
&= n – \lr{ n – 1} \\
&= 1 \\
\Delta n^2
&= n^2 – \lr{ n – 1}^2 \\
&= 2 n – 1 \\
\Delta n^3
&= n^3 – \lr{ n – 1}^3 \\
&= 3 n^2 – 3 n + 1.
\end{aligned}
\end{equation}
Rearranging, we find
\begin{equation}\label{eqn:sumOfSquares:101}
\begin{aligned}
1 &= \Delta n \\
n &= \inv{2} \lr{ \Delta n^2 + 1 } \\
&= \inv{2} \lr{ \Delta n^2 + \Delta n } \\
&= \inv{2} \Delta \lr{ n^2 + n } \\
n^2
&= \inv{3} \lr{ \Delta n^3 + 3 n – 1 } \\
&= \inv{3} \lr{ \Delta n^3 + \frac{3}{2} \Delta \lr{ n^2 + n } – \Delta n } \\
&= \inv{6} \Delta \lr{ 2 n^3 + 3 \lr{ n^2 + n } – 2 n } \\
&= \inv{6} \Delta \lr{ 2 n^3 + 3 n^2 + n }.
\end{aligned}
\end{equation}

Sum of squares.

We can now proceed to find the difference of our sum of squares sequence. Let
\begin{equation}\label{eqn:sumOfSquares:121}
y_n = \sum_{k = 1}^n,
\end{equation}
for which we have
\begin{equation}\label{eqn:sumOfSquares:141}
\Delta y_n = n^2 = \Delta \frac{2 n^3 + 3 n^2 + n }{6}.
\end{equation}
Akin to integrating, we’ve determined \( y_n \) up to a constant
\begin{equation}\label{eqn:sumOfSquares:161}
y_n = \frac{2 n^3 + 3 n^2 + n }{6} + C,
\end{equation}
but since \( y_1 = 1 \), and
\begin{equation}\label{eqn:sumOfSquares:181}
y_1 = \frac{2 \times 1^3 + 3 \times 1^2 + 1 }{6} + C = 1 + C,
\end{equation}
so \( C = 0 \). We need only factor to find the desired result
\begin{equation}\label{eqn:sumOfSquares:201}
\sum_{k = 1}^n k^2 = \frac{n}{6}\lr{ 2 n + 1 }\lr{ n + 1 }.
\end{equation}

Sum of cubes.

Let’s also apply this to compute a formula for the sum of cubes. We need one more difference computation

\begin{equation}\label{eqn:sumOfSquares:221}
\begin{aligned}
\Delta n^4
&= n^4 – \lr{ n – 1 }^4 \\
&= 4 n^3 – 6 n^2 + 4 n – 1,
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:sumOfSquares:241}
\begin{aligned}
n^3 &= \inv{4} \lr{ \Delta n^4 + 6 n^2 – 4 n + 1 } \\
&= \inv{4} \lr{ \Delta n^4 + \Delta \lr{ 2 n^3 + 3 n^2 + n } – 2 \Delta \lr{ n^2 + n } + \Delta n } \\
&= \inv{4} \Delta \lr{ n^4 + 2 n^3 + n^2 },
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:sumOfSquares:261}
\sum_{k=1}^n n^3 = \inv{4} \lr{ n^4 + 2 n^3 + n^2 } + C,
\end{equation}
but we see that \( C = 0 \) is required to satisfy the \( n = 1 \) case. That is
\begin{equation}\label{eqn:sumOfSquares:281}
\sum_{k=1}^n n^3 = \inv{4} n^2 \lr{ n + 1 }^2.
\end{equation}

Difference calculus is a pretty fun tool!

References

[1] Hyman Levy and Freda Lessman. Finite difference equations. Courier Corporation, 1992.