Writing is thinking. To write well is to think clearly. That's why it's so hard.

~ David McCullough
 

Deriving the Sum of Squares Formula

2017年07月21日

As we talked about last time, for two consecutive numbers $n$ and $m$ (with $m$ the larger of the two), the difference of their squares is given by $m^2 - n^2 = 2n + 1$.

If you thought about this long enough, you might start to wonder, would this trick still work if we used a difference of consecutive cubes instead? It might look something like this:

$$ \require{cancel} \begin{array}{rrcrr} & 6^3 - \cancel{5^3} & & \\ + & \cancel{5^3} - \cancel{4^3} & & \\ + & \cancel{4^3} - \cancel{3^3} &=& ?\\ + & \cancel{3^3} - \cancel{2^3} & & \\ + & \cancel{2^3} - \cancel{1^3} & & \\ + & \cancel{1^3} - \cancel{0^3} & & \end{array} $$

If only we knew a nice way to express quantities involving cubes such as $5^3 - 4^3$ like we did for quantities involving squares.

Since $m$ is one greater than $n$, we can substitute $n+1$ for $m$ in the expression $m^3 - n^3$. This results in the expression $(n+1)^3 - n^3$.

To dig into this problem, we need to express the quantity $(n+1)^3$ in a more useful form. We can do this using the binomial theorem:

$$ (x + y)^n = \sum_{k=0} \binom{n}{k} x^k y^{n-k} $$

Where the symbol $\binom{n}{k} = \frac{n!}{k! (n-k)!}$ is the $(n, k)^{\text{th}}$ binomial coefficient.

In the special case that we need, this gives us $(n + 1)^3 = n^3 + 3n^2 + 3n + 1$. And to put it all together, we have:

$$ (n+1)^3 - n^3 = 3n^2 + 3n + 1 $$

In effect, we have just expanded $(n+1)^3$ and "chopped off" the first term, so I will be writing this as follows throughout:

$$ (n+1)^3 - n^3 = \cancel{n^3} + 3n^2 + 3n + 1 $$

Now, we can make progress on our original idea:

$$ \begin{array}{rrcrr} & 6^3 - \cancel{5^3} & & \cancel{5^3} + 3 \cdot 5^2 + 3 \cdot 5 + 1 \\ + & \cancel{5^3} - \cancel{4^3} & & \cancel{4^3} + 3 \cdot 4^2 + 3 \cdot 4 + 1 \\ + & \cancel{4^3} - \cancel{3^3} &=& \cancel{3^3} + 3 \cdot 3^2 + 3 \cdot 3 + 1\\ + & \cancel{3^3} - \cancel{2^3} & & \cancel{2^3} + 3 \cdot 2^2 + 3 \cdot 2 + 1 \\ + & \cancel{2^3} - \cancel{1^3} & & \cancel{1^3} + 3 \cdot 1^2 + 3 \cdot 1 + 1 \\ + & \cancel{1^3} - \cancel{0^3} & & \cancel{0^3} + 3 \cdot 0^2 + 3 \cdot 0 + 1 \end{array} $$

We can now add vertically, as we did last time, to get:

$$ 6^3 = 3\cdot(1^2 + 2^2 + 3^2 + 4^2 + 5^2) + 3 \cdot (1 + 2 + 3 + 4 + 5) + 6 $$

Seeing the pattern clearly

We can take this equation and alter it very slightly in a way which makes the pattern very clear. We start counting at $0$ rather than $1$, and we expand the $6$ at the end as the sum of the $0^{\text{th}}$ powers. (We also write the first powers explicitly). The result is quite pleasing to look at, even though it's not necessary for computation:

$$ \begin{array}{lrl} 6^3 =& &3 \cdot (0^2 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2) \\ & +&3 \cdot (0^1 + 1^1 + 2^1 + 3^1 + 4^1 + 5^1) \\ & +&\ \ \ \ \ (0^0 + 1^0 + 2^0 + 3^0 + 4^0 + 5^0) \end{array} $$

The $6$ on the left hand side reminds us that we're thinking about the first $6$ integers, when we count starting from $0$. The $3$'s we see as coefficients in front of the sums are actually the binomial coefficients, $\binom{3}{1} = 3$ and $\binom{3}{2} = 3$. There is no coefficient for the last term, since $\binom{3}{3} = 1$.

Continuing on...

So we currently have this equation sitting in front of us:

$$ 6^3 = 3\cdot(1^2 + 2^2 + 3^2 + 4^2 + 5^2) + 3 \cdot (1 + 2 + 3 + 4 + 5) + 6 $$

We can see we have an expression involving the sum of the first $5$ consecutive integers $(1 + 2 + 3 + 4 + 5)$ and their squares $(1^2 + 2^2 + 3^2 + 4^2 + 5^2)$. We don't know anything about the sum of the squares, but we do know how to quickly calculate the sum of the integers themselves: $(1 + 2 + 3 + 4 + 5) = \frac{5\cdot (5+1)}{2} = 15$, as we discussed last time. And so we can substitute:

$$ 6^3 = 3\cdot(1^2 + 2^2 + 3^2 + 4^2 + 5^2) + 3 \cdot 15 + 6 $$

And so we could use a little bit of algebra and solve for $1^2 + 2^2 + 3^2 + 4^2 + 5^2$.

Generalizing to the sum of the first $n$ squares

And moreover, this trick would work for more than $5$. In general, we get:

$$ \begin{align} (n+1)^3 &= 3\cdot (1^2 + 2^2 + 3^2 + \cdots + n^2) + 3\cdot (1 + 2 + 3 + \cdots + n) + (n+1) \\ &= 3\cdot (1^2 + 2^2 + 3^2 + \cdots + n^2) + 3\cdot \frac{n(n+1)}{2} + (n+1) \end{align} $$

From this point on, it's just a lot of messy algebra. If you isolate the sum of squares on the left hand side, you will arrive any of these equivalent, tidy formulas:

$$ \begin{align} 1^2 + 2^2 + 3^2 + \cdots + n^2 &= \frac{1}{3} n^3 + \frac{1}{2} n ^2 + \frac{1}{6} n \\\\ &= \frac{2n^3 + 3n^2 + n}{6} \\\\ &= \frac{n(n+1)(2n+1)}{6} \end{align} $$

Tada! While the naive sum requires computing $n$ squares and then $n-1$ additions, we can instead arrive at the same result with only a single cube, a single square, three divisions, and two additions. When $n$ is large (say, in the tens or hundreds), this saves us quite a bit of computing.

Generalizing to higher powers

The algebra is tedious, but conceptually it is no harder to apply this same trick to higher powers than it is for squares.

For computing the sum of cubes, you would use $(n+1)^4 - n^4 = \cancel{n^4} + 4 n^3 + 6 n^2 + 4n + 1$ and play the same trick, adding vertically, cancelling out terms as you go.

With enough work, you can work out a formula for each power. Here are the first few:

$$ \begin{align} 1 + 2 + 3 + \cdots + n &= \frac{1}{2}n^2 + \frac{1}{2}n \\\\ 1^2 + 2^2 + 3^2 + \cdots + n^2 &= \frac{1}{3} n^3 + \frac{1}{2} n ^2 + \frac{1}{6} n \\\\ 1^3 + 2^3 + 3^3 + \cdots + n^3 &= \frac{1}{4} n^4 + \frac{1}{2} n ^3 + \frac{1}{4} n^2 \\\\ 1^4 + 2^4 + 3^4 + \cdots + n^4 &= \frac{1}{5} n^5 + \frac{1}{2} n ^4 + \frac{1}{3} n^3 - \frac{1}{30} n\\\\ 1^5 + 2^5 + 3^5 + \cdots + n^5 &= \frac{1}{6} n^6 + \frac{1}{2} n ^5 + \frac{5}{12} n^4 - \frac{1}{12} n^2\\\\ \end{align} $$

You'll notice a few patterns among them. In 1713, mathematician Jakob Bernoulli wrote about these patterns and discovered an important sequence of numbers buried inside the coefficients. These numbers, which are now called Bernoulli Numbers, appear in many curious places in analysis and number theory.

qed