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

~ David McCullough
 

Another Approach to Gauss's Trick

2017年07月11日

We talked last time about the problem of summing the first $n$ consecutive integers. Here is another approach which demonstrates some different, but equally clever tricks. $\require{cancel}$

In high school, we learn that the difference of two squares can be computed by the formula $m^2 - n^2 = (m+n)(m-n)$. If this is unfamiliar, try expanding the right hand side and then simplifying.

Let's suppose for a moment that $m$ is the next number after $n$. We compute that:

$$ \begin{align} m^2 - n^2 &= (m+n)(m-n) \\ &= (2n + 1)(1) \\ &= 2n + 1 \end{align} $$

This formula holds for all $n$ whenever $m$ is the next number up. This means we can instantiate the formula with different values for $n$ like this:

$$ \begin{align} 6^2 - 5^2 = 2 \cdot 5 + 1 \\ 5^2 - 4^2 = 2 \cdot 4 + 1 \\ 4^2 - 3^2 = 2 \cdot 3 + 1 \\ 3^2 - 2^2 = 2 \cdot 2 + 1 \\ 2^2 - 1^2 = 2 \cdot 1 + 1 \\ 1^2 - 0^2 = 2 \cdot 0 + 1 \end{align} $$

This is where we get clever. We add vertically. Something interesting happens on either side of the equals sign.

Cancellation on the left, grouping on the right

On the left of the equals sign, you'll notice that the first term in each line cancels with the second term on the line before it.

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

On the right hand side, we see that we have six $1$'s and twice the sum of the first five integers (six if you think of it as starting with $0$). Putting it all together, we get:

$$ \begin{align} 6^2 = 2 \cdot (1 + 2 + 3 + 4 + 5) + 6 \end{align} $$

I used the number $5$ here for concreteness, but I could have used the same trick starting at any number $n$ and walking my way down to $0$. In general, the formula looks like this:

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

From this point, it is a simple matter of algebra to work out the sum of the first $5$ consecutive integers:

$$ 1 + 2 + 3 + 4 + 5 = \frac{6^2 - 6}{2} $$

Or in general, to solve for the sum of the first $n$ integers:

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

There are certainly easier ways to arrive at this formula. Following the reasoning from the previous post, you could have easily worked it out for yourself. But I'm presenting it this way because by modifying this technique, we will be able to work out sums of squares of consecutive integers as well as sums of higher powers.

Triangle Numbers

The numbers you get from summing $1 + 2 + 3 + \cdots + n$ are very common in mathematics and they have a name. The are the Triangle Numbers. They get their name from the fact that given a triangular number objects, you can arrange them in a triangle shape. This is familiar to anyone who has ever bowled or played pool.

They also appear very naturally outside of geometry, too. If you have a group with $n$ people and you want everyone to shake everyone elses' hand, how many handshakes will their be? Well, you have the first person shake everyone elses' hand for a total of $n-1$ handshakes. Then the second person goes around and shakes everyone's hand except the first person (those two have already shaken hands). This adds another $n-2$ handshakes. The third person shakes everyone's hand except the two that they already have shaken for $n-3$ more. And so on. In all, you end up with $(n-1) + (n-2) + (n-3) + \cdots + 3 + 2 + 1$ handshakes. (You can reverse the order you add things in to see it's just $1 + 2 + 3 + \cdots + (n-1)$).

You may happen to know that some simple sorting algorithms, such as insertion sort, require $\mathcal{O}(n^2)$ operations. This is due to the fact that these sorts might end up comparing each element in the list to each other element, which gives us a situation much like the handshakes. The $n^2$ in $\mathcal{O}(n^2)$ comes up because our final formula, $\frac{(n+1)n}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$ is a quadratic function.

As a final fun fact, even perfect numbers are always triangle numbers.

qed