Gauss's pairing trick, and why it generalises

0:00On a first birthday, a hundred goes into a savings jar. On the next birthday, a hundred and fifty. On the one after that, two hundred. Then two hundred and fifty. Every year the deposit is fifty more than the year before, and that goes on until the twenty-first birthday. So the deposits are a progression. First entry a hundred, step fifty, twenty-one entries in all. The last one is a hundred with twenty steps of fifty piled on top of it, which is eleven hundred.

0:35But the question is not about any single deposit. The question is what the jar holds once the last one has gone in. That is the total of all twenty-one, and nothing we have so far will hand it over. There is an honest way to answer, and it is to add them up. A hundred. Then two hundred and fifty. Then four hundred and fifty. Then seven hundred. Then a thousand.

1:04Five deposits in, four additions done, and most of the list still ahead of us. Twenty additions altogether, and every one of them a chance to slip. It is not that it cannot be done. It is that it is a chore, and a chore does not scale. Ask for a hundred entries and it is ninety-nine additions. Ask for a thousand and it is nine hundred and ninety-nine. Ask for a million and nobody is going to do it at all.

1:36What we want is a route to the total whose cost does not grow with the list. There is an old story about a boy named Gauss. He was asked, along with the rest of his class, to add the whole numbers from one up to a hundred. Everyone else began adding. He wrote down five thousand and fifty, and stopped. Take the story for what it is worth. The interesting part is not who he was; it is what he could have seen.

2:07Five thousand and fifty is not a number anyone guesses. Something about that list gave it up quickly. And whatever that something is, it had better not be about the numbers one to a hundred in particular, or it is a trick with no future. Here is the move. Write the total out. One plus two plus three, all the way up to ninety-eight, ninety-nine, a hundred. Now write it out again underneath. The same total, the same numbers, but backwards.

2:42A hundred, ninety-nine, ninety-eight, running all the way down to three, two, one. Nothing has been claimed yet. The second row is the first row with its numbers in another order, so it carries the same total, whatever that total turns out to be. What has changed is what sits above what. The two rows are lined up in columns now, and each column holds one entry from the front of the list and one from the back.

3:14Look along the columns. The first holds one and a hundred. That is a hundred and one. The second holds two and ninety-nine. A hundred and one again. The third holds three and ninety-eight. A hundred and one. You could call that a coincidence about the number a hundred and one, and if you did, the trick would stop here. It is not a coincidence, and here is the reason.

3:41Move one place to the right along the top row and the entry goes up by one. Move that same one place to the right along the bottom row and the entry goes down by one, because the bottom row is running the other way. One rises by exactly what the other falls by, so the column total does not move at all. That is the whole argument, and notice what it leaned on. Every step along this list is the same size.

4:14Now count. There are a hundred columns, because there were a hundred entries, and each column is a hundred and one. A hundred lots of a hundred and one is ten thousand one hundred. That is not the total, though. It is the total twice over, because we wrote the list down twice. So halve it. Five thousand and fifty. The division by two is not a rule anyone has to remember. It undoes the writing out twice, and nothing else.

4:47And notice what the counting replaced. We never added a hundred numbers. We added one column, counted the columns, and multiplied. Before taking that to a general list, it is worth pulling the move apart, because it has two halves and only one of them is doing hard work. The first half. Stacking a list against its own reverse always gives twice the total. That is not a theorem about progressions. The bottom row holds exactly the same numbers as the top row, in another order, so the two rows together hold the total twice. It is free, and it is true of any list at all.

5:32The second half is the one that mattered. Every column came to the same amount. That is what let us count the columns instead of adding them, and counting and multiplying is the only reason any of this is faster than adding. So the question to carry forward is a sharp one. What makes the columns agree? Take a progression written in the general way. First entry a. Then a plus d. Then a plus two d. And onwards, up to a plus n minus one d, which is the entry standing in position n.

6:11Write that row out, and write it out again backwards underneath, exactly as before. The lower row opens at a plus n minus one d and comes down by d each time, ending at a. We have no particular numbers to add now, so we cannot check the columns one at a time. We have to look at a column in general. Take the column standing in position k, where k could be any position from one to n.

6:42The top of that column is the kth entry, which is a plus k minus one d. The bottom of it is the kth entry counted from the other end. Counting from the back, the kth one stands in position n minus k plus one, so it is a plus n minus k d. Add them. The two a terms give two a. The step terms give k minus one, plus n minus k, all times d. The k and the minus k cancel, and what is left is n minus one.

7:19So the column comes to two a plus n minus one d. Read that again and notice what is missing. There is no k in it. The column does not depend on which column it is, which is exactly what the hundred and ones were telling us. And had we copied the row out forwards instead of backwards, the column would have been two a plus two times k minus one d, with the k still sitting in it. The reversal is what removes it.

7:52Now the counting, and it goes the same way it went before. There are n columns, and every one of them is two a plus n minus one d. So the stack comes to n times, in brackets, two a plus n minus one d. And that is twice the total, because we wrote the list twice. Halve it, and there is the result. The sum of the first n entries is n over two, times two a plus n minus one d.

8:22There is a second way to wear the same formula. Two a plus n minus one d is a, plus a plus n minus one d, which is the first entry plus the last. So the total is n over two times the first entry plus the last, which is what the columns were saying all along. Where exactly did the constant step get used, and what happens without it?

8:50Take a list that is not a progression. One, one, two, three, five, eight, where each entry is the two before it added together. Stack it against its own reverse and read the columns. Nine. Six. Five. Five. Six. Nine. The first half of the move survived. Those columns add to forty, which is twice twenty, and twenty is the true total. The doubling never needed anything. The second half is gone. Three different amounts, so there is nothing to count.

9:25And if you pressed on anyway, six columns of nine, halved, would hand you twenty-seven. The list adds to twenty. The columns have to agree, or the counting has nothing to count. So what does the derivation actually need? Not the constant step by name. It needs the columns to agree. A constant step is what guarantees they will, and here is the fine print. It is not the only thing that can.

9:56Look at nought, one, three, four. The steps are one, then two, then one, so this is not a progression at all. But its columns are four, four, four and four. Every one the same. Four columns of four, halved, is eight, and nought and one and three and four do add to eight. The move works on it. It works by luck rather than by guarantee, and you only find that out by checking every column.

10:26Which is what a constant step really buys. You do not have to check. Back to the jar. First entry a hundred, step fifty, twenty-one entries. The last deposit is a hundred with twenty steps of fifty on it, which is eleven hundred. So a column holds a hundred and eleven hundred, which is twelve hundred, and each of the twenty-one columns holds twelve hundred. Twenty-one lots of twelve hundred is twenty-five thousand two hundred.

11:00Halve it. Twelve thousand six hundred, and that is what the jar holds. Notice that twenty-one is odd. Nothing here paired an entry off against another entry; we stacked two whole copies of the list, so an odd count is no obstacle. And notice what the answer is not. It is not the last deposit, which was eleven hundred. It is everything that ever went in. Two ways to lose it, both worth naming.

11:31Write n where n minus one belongs and the jar comes out at thirteen thousand one hundred and twenty-five, which is five hundred and twenty-five too much. That five hundred and twenty-five is half of twenty-one steps of fifty. Forget the halving and you get twenty-five thousand two hundred, which is the stack, not the total. What we have is this. Write the total out, write it out again backwards, and stack the two.

12:02Every column is the first entry plus the last, because one row rises by exactly what the other falls by. Count the columns, multiply, and halve, with the halving undoing the second copy. The sum of the first n entries is n over two times two a plus n minus one d, or n over two times the first plus the last, whichever you have to hand. And it reproduces where it came from. First entry one, step one, a hundred entries gives fifty times a hundred and one, which is five thousand and fifty.

12:43The point of a formula is that it answers where nobody can walk. One plus two, onwards to a million, is five hundred billion, five hundred thousand, and that is one multiplication rather than a million additions.