The Sum of the Sum of Some Numbers

Subtitle: Anarchic Meets Impromptu

Carl Gauss’ Very Bad Day

Johann Carl Friedrich Gauss has been called the Princeps mathematicorum (Latin for “the foremost of mathematicians” and anagram of “Anarchic Meets Impromptu”). He made many contributions to mathematics and science, and the British mathematician Henry John Stephen Smith said of Gauss,

If we except the great name of Newton it is probable that no mathematicians of any age or country have ever surpassed Gauss in the combination of an abundant fertility of invention with an absolute rigorousness in demonstration, which the ancient Greeks themselves might have envied.

Carl_Friedrich_Gauss_1840_by_Jensen

An apocryphal story of Gauss is that his teacher J.G. Büttner gave him detention for misbehaving in class, and told Gauss that he could go home when he’d added up all the numbers from 11 to 100100. Gauss immediately said 50505050, and went home. Much later, Gauss’ picture appeared on the German 10-Deutche Mark note.

Johnny von Neumann’s Train Wreck

A similar story about mathematician John von Neumann is that he was at a party one time when someone asked him to solve a train problem.

john-von-neumann

One train leaves New York heading toward Chicago and a second train leaves at the same time from Chicago for New York. (Stop me if you’ve heard this one before.) The distance between Chicago and New York is 800800 miles and both trains travel at 100  mph100 \; \text{mph}.

A very fast bee going 150 mph150 \text{ mph} takes off from the front of the NY to CHI train just as the train leaves the station (going 100 mph100 \text{ mph}) and flies until it reaches the CHI to NY train. At that moment, it turns around and returns to the first train.

This continues until the trains meet in the middle, and due to a switching error, they’re both on the same track and the bee gets squished in the wreckage. The problem was to figure out the total distance the bee flew on its final, fateful journey. You need to account for the positions of each train when the bee arrives and turns around.

avoid-train-wreck

John von Neumann instantly answered “600 miles”.

“Oh, you must have known the trick” the other person said.

“What trick?” von Neumann asked, “I just summed up all of the individual distances.”

There are an infinite number of distances between the trains as they approach each other, each distance smaller than the previous one. Von Neumann had to add them all together, and it’s a bit like Zeno’s “Achilles and the Tortoise” paradox.

The trick is that since both trains are going 100 mph100 \text{ mph} and the distance is 800800 miles, then when they crash into each other, they’ll both have gone 400400 miles, taking 44 hours. Since the bee flies at 150 mph150 \text{ mph} then its total distance would be 600600 miles.

I won’t try to explain how von Neumann added up an infinite number of distances in his head so quickly, but we can understand how Gauss solved his detention problem. Think of the numbers arranged in a line, and connect the 11 with 100100, 22 with 9999, 33 with 9898, and so on.

sum-of-100

Then the sum of 1+100=1011 + 100 = 101, 2+99=1012+99 = 101, 3+98=1013 + 98 = 101, and the final pair is 50+51=10150 + 51 = 101. Since there are 5050 pairs of 101101 then you can multiply 50×100=500050 \times 100 = 5000 and add 5050 to get the total 50505050. You can check that the formula for the sum of the first nn numbers is S=12n(n+1)S = \frac{1}{2}n(n+1).

Doubling Down on Gauss

A somewhat more complicated version of Gauss’ detention problem is this. Suppose you have nn numbered tiles with numbers ranging from 1,2,,n1,2, \ldots, n. Add up all possible pairs and you’ll get either the total sum S1=3,165,720S_1 = 3,165,720 or S2=3,165,620S_2 = 3,165,620.

The question is, which is the correct total sum S1S_1 or S2S_2, and what is the value of nn? Daniel Hardisky proposed this problem for the Classical Mathematics Facebook group.

tiles

Let’s start with an easy case, n=3n=3. Then, we have to add the pairs together, (1+2)+(2+3)+(3+1)=12(1+2) + (2+3) + (3+1) = 12. Notice that each number appears twice, so we could have doubled 1+2+3=61+2+3 = 6.

Maybe it’s just that easy. Let’s try n=4n=4. If we combine sequentially, we get (1+2)+(2+3)+(3+4)+(4+1)=20(1+2) + (2+3) + (3+4)+(4+1) = 20, but we’ve left out (1+3)(1+3) and (2+4)(2+4) which increases the final sum to 3030.

How many ways can we combine two numbered tiles in a pile of nn tiles? This is a combinatorics problem and the answer is

N=(nk)=n!(nk)!k!N = \binom{n}{k} = \frac{n!}{(n-k)!k!}

where n!=n(n1)(n2)321n! = n(n-1)(n-2) \cdots 3 \cdot 2 \cdot 1. For the case of choosing k=2k=2 different tiles at a time, this simplifies to

N=12n(n1).N = \frac{1}{2}n(n-1).

Scientific computer languages have built-in functions to calculate the number of combinations for different values of nn and kk, in Julia, it’s binomial(n,2), in R, use choose(n,k), and Python calls scipy.special.comb(n, k).

Octave also calculates the binomial expansion with nchoosek(n,k), but has a feature not found in other languages - you can replace nn with a vector to show all of the possible combinations of nn numbers taken kk at a time. The notation 1:5 is a vector containing the first 55 integers, so we can have Octave return all of the combinations taken 22 at a time,

>> nchoosek(1:5,2)
ans =

1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Even better, if we add the numbers in each row, we get every possible pair sum, and then adding those sums gives the total.

>> sum(sum(nchoosek(1:5,2)))
ans = 60

Maybe we can arrange the numbers to be similar to the way Gauss did his sum. If we add up all possible pairs for n=5n=5, we can arrange them in descending order like this:

S=(5+4)+(5+3)+(5+2)+(5+1)+(4+3)+(4+2)+(4+1)+(3+2)+(3+1)+(2+1).\begin{aligned} S = (5+4) + (5+3) + (5+2) &+ (5+1) \\ + (4+3) + (4+2) &+ (4+1) \\ + (3+2) &+ (3+1) \\ &+ (2+1). \end{aligned}

Notice the first line has four 55s and the sum 1+2+3+41+2+3+4. So, the top line is 4×5+(1+2+3+4)=20+10=304 \times 5 + (1+2+3+4) = 20 + 10 = 30. It’s an easy multiplication followed by a sum using Gauss’ trick. The next line is the same, but shorter, 4×3+(1+2+3)=12+6=184 \times 3 + (1+2+3) = 12 + 6 = 18.

For nn numbers the sum becomes

S=(n+(n1))+(n+(n2))++(n+2)+(n+1)+((n1)+(n2))+((n1)+(n3))++((n1)+2)+((n1)+1)+(5+4)+(5+3)+(5+2)+(5+1)+(4+3)+(4+2)+(4+1)+(3+2)+(3+1)+(2+1).\begin{aligned} S = (n+(n-1)) + (n+(n-2))+ \cdots +(n+2) &+ (n+1) \\ + ((n-1)+(n-2)) + ((n-1)+(n-3))+ \cdots + ((n-1) + 2) &+ ((n-1)+1) \\ \vdots \\ + (5+4) + (5+3) + (5+2) &+ (5+1) \\ + (4+3) + (4+2) &+ (4+1) \\ + (3+2) &+ (3+1) \\ &+ (2+1). \\ \end{aligned}

If we collect all of the individual nn terms in the top two lines there are n1n-1 of them, and then what’s left is the sum of 1+2+3++(n1)1+2+3 + \cdots + (n-1), which can be written as

n(n1)+j=1n1j=n(n1)+12(n1)n.n(n-1) + \sum_{j=1}^{n-1}j = n(n-1) + \frac{1}{2}(n-1)n.

The total sum for all of the terms is

S=S(n)=(n(n1)+j=1n1j)+((n1)(n2)+j=1n2j)++(43+j=141j)+(32+j=131j)+(21+j=121j).\begin{aligned} S = S(n) = \left( n \cdot (n-1) + \sum_{j=1}^{n-1}j \right) + \left( (n-1) \cdot (n-2) + \sum_{j=1}^{n-2}j \right) + \cdots \\ + \left( 4 \cdot 3 + \sum_{j=1}^{4-1}j \right) + \left( 3 \cdot 2 + \sum_{j=1}^{3-1}j \right) + \left( 2 \cdot 1 + \sum_{j=1}^{2-1}j \right). \end{aligned}

Now we can sum up all of the individual terms,

S(n)=k=1n1(k(k+1)+j=1kj).S(n) = \sum_{k=1}^{n-1}\left(k(k+1) + \sum_{j=1}^k j \right).

Since j=1kj=12k(k+1)\sum_{j=1}^k j = \frac{1}{2} k(k+1), this can be expressed as

S(n)=k=1n1(k(k+1)+12k(k+1))=32k=1n1k(k+1)=32k=1n1k2+32k=1n1k=32k=1n1k2+32(12(n1)n).\begin{aligned} S(n) &= \sum_{k=1}^{n-1}\left(k(k+1) + \frac{1}{2}k(k+1)\right) \\ &= \frac{3}{2}\sum_{k=1}^{n-1} k(k+1) \\ &= \frac{3}{2}\sum_{k=1}^{n-1} k^2 + \frac{3}{2}\sum_{k=1}^{n-1} k \\ &= \frac{3}{2}\sum_{k=1}^{n-1} k^2 + \frac{3}{2} \left( \frac{1}{2} (n-1)n \right). \end{aligned}

Squared Pictures

This is a pretty compact formula for S(n)S(n), the sum of all possible pairs of the numbers from 11 to nn. But, can we find a better way to express k=1n1k2\sum_{k=1}^{n-1}k^2? The first five squares are 1,4,9,16,251,4,9,16,25, and the sums are 1,5,14,30,551,5,14,30,55.

Here’s a neat visual proof from the Math and Multimedia website. Make a stack of the first nn squares like this:

sum-of-squares1

Next, make three copies of this stack,

sumofsquares2

and fit them together to make a cube, except the red stack will extend one layer above the green and yellow stacks.

sum-of-squares-4

If you slice the top layer of the red pyramid in half and flip it over, you can fill in the missing part:

sum-of-squares-5

which lets us calculate the total volume,

sum-of-squares-6

so we might expect the formula is

k=1nk2=13n(n+1)(n+12)=16n(n+1)(2n+1).\begin{aligned} \sum_{k=1}^n k^2 &= \frac{1}{3}n(n+1)(n+\frac{1}{2}) \\ &= \frac{1}{6}n(n+1)(2n+1). \end{aligned}

The Proof

Pictures are helpful, but they aren’t considered mathematical proofs. There are many ways to construct a mathematical proof, but one that gets used frequently is called “Proof by Induction”.

Suppose you have a formula you think is correct, and you check it for the case n=1n=1. If that holds, then show it holds for any n1n-1, and add the nthn^{th} term to see if the formula still holds. Let’s make this a bit more formal.

Theorem: The sum of the first nn squares is

k=1nk2=16n(n+1)(2n+1).\sum_{k=1}^{n} k^2 = \frac{1}{6}n(n+1)(2n+1).

Proof: For n=1n=1,

12=1=16(1)(1+2)(21+1)=16(1)(2)(3)=1.1^2 = 1 = \frac{1}{6}(1)(1+2)(2\cdot1+1) = \frac{1}{6}(1)(2)(3) = 1.

Assume the formula holds for the case n1n-1,

k=1n1k2=16(n1)(n)(2(n1)+1)=16n(n1)(2n1).\begin{aligned} \sum_{k=1}^{n-1} k^2 &= \frac{1}{6}(n-1)(n)(2(n-1)+1) \\ &= \frac{1}{6}n(n-1)(2n-1). \end{aligned}

Then the sum of the first nn squares is

k=1n1k2+n2=16n(n1)(2n1)+n2=16n(2n23n+1)+n2=16(2n33n2+n)+16(6n2)=16(2n3+3n2+n)=16n(2n2+3n+1)=16n(n+1)(2n+1).  \begin{aligned} \sum_{k=1}^{n-1}k^2 + n^2 &= \frac{1}{6}n(n - 1)(2n-1) + n^2 \\ &= \frac{1}{6} n (2n^2 -3n + 1) + n^2 \\ &= \frac{1}{6} (2n^3 -3n^2 + n) + \frac{1}{6}(6n^2) \\ &= \frac{1}{6} (2n^3 +3n^2 + n) \\ &= \frac{1}{6} n(2n^2 + 3n + 1) \\ &= \frac{1}{6} n(n+1)(2n + 1). \; \blacksquare \\ \end{aligned}

The inductive part of this proof is that we didn’t specify a value for nn, so it can be any integer.

We showed the formula holds for n=1n=1 in the first part, so it must hold for n=2n=2 by the second part. Since it holds for n=2n=2, then it must also be true for n=3n=3 and so on.

The Formula Simplified

And now, we have a complete formula for the sum of all possible pairs of the first nn numbers,

S(n)=32(16n(n1)(2n1)+12n(n1))=32(16(n2n)(2n1)+12(n2n))=32(16(2n33n2+n)+16(3n23n))=32(16(2n32n))=12(n3n).\begin{aligned} S(n) &= \frac{3}{2} \left( \frac{1}{6} n(n-1)(2n-1) + \frac{1}{2}n(n-1) \right) \\ &= \frac{3}{2} \left( \frac{1}{6} (n^2-n)(2n-1) + \frac{1}{2}(n^2-n) \right) \\ &= \frac{3}{2} \left( \frac{1}{6} (2n^3 -3n^2+n) + \frac{1}{6}(3n^2-3n) \right) \\ &= \frac{3}{2} \left( \frac{1}{6} (2n^3 - 2n) \right) \\ &= \frac{1}{2} (n^3 - n). \\ \end{aligned}

Tartaglia’s Depression

Niccolò Fontana Tartaglia was a 16th16^{th}-century mathematician and engineer from Venice.

niccolò-fontana-tartaglia

Tartaglia found a neat trick to convert a general cubic equation, ax3+bx2+cx+dax^3 + bx^2 + cx + d into a simpler form where the x2x^2 term disappears. By substituting x=yb3ax = y - \frac{b}{3a}, he got the “depressed cubic” y3+Ay=By^3 + Ay = B.

With a bit of rearrangement, we can get our sum into the depressed cubic form,

n3n=2S,n^3 - n = 2S,

where A=1A = -1 and B=2SB = 2S. In this form, the solution for nn is n=stn = s - t where

3st=As3t3=B.\begin{aligned} 3st &= A \\ s^3 - t^3 &= B. \end{aligned}

You can check this with a simple substitution. If we put t=13st = -\frac{1}{3s} from the first equation into the second, we get

s3+127s3=2Ss62Ss3+127=0.\begin{aligned} s^3+\frac{1}{27s^3} = 2S \\ s^6 - 2Ss^3 + \frac{1}{27} = 0. \end{aligned}

Substituting u=s3u=s^3 gives the quadratic

u22Su+127=0u^2 - 2Su + \frac{1}{27} = 0

with solutions

u=12(2S±4S2+427)=S±S2+127.\begin{aligned} u &= \frac{1}{2}\left(2S \pm \sqrt{4S^2 + \frac{4}{27}}\right) \\ &= S \pm \sqrt{S^2 + \frac{1}{27}}. \end{aligned}

Then, s=u3s = \sqrt[3]{u} and n=s+13sn = s + \frac{1}{3s}. Solving for S1=3165720S_1 = 3165720 gives n1=185n_1 = 185, while S2=3165620S_2 = 3165620 gives n2=184.99805n_2 = 184.99805, so the first sum is the correct solution.

The Octave function depressedCubic.m calculates the solution for any depressed cubic in the form x3+Ax=Bx^3 + Ax = B.

Abel and the Terrible, Horrible, No Good, Very Bad Day

Niels Henrik Abel was a Norwegian mathematician who made many contributions to mathematics, and said of Gauss “He is like the fox, who effaces his tracks in the sand with his tail.”

The Abel Prize, named in his honor is the mathematical equivalent of the Nobel Prize, and his picture appears on the Norwegian 500 kroner banknote.

NOK_500_V_recto

One of Abel’s great contributions to mathematics was his proof that there is no closed-form solution to the quintic equation,

ax5+bx4+cx3+dx+e=0,ax^5 + bx^4 + cx^3 + dx + e = 0,

which had been an open problem for 250 years. All in all, it was a great day for Abel, but a lousy day for anyone hoping to solve the equation directly, and we now know that no formula exists for the solution to fifth-order and higher polynomials.

Luckily, our problem involves only the quadratic formula and the solution to the depressed cubic.

If you’re feeling adventurous, you could try finding a formula for the sum of all possible combinations of the first nn integers taken three at a time, four at a time, and so on. Of course, if you take them nn at a time, you’re back to the beginning and the sum is 12n(n+1)\frac{1}{2}n(n+1).