PROFESSOR: So now we start on a new unit called counting or combinatorics. And it's about counting things. Now one of the things that happens when you're counting is your typically adding up a bunch of numbers that you've counted along the way. And so you wind up needing to deal with sums a lot. And so let's start with those mathematical preliminaries.
We're going to look at three kinds of sums, arithmetic sums, geometric sums, and harmonic sums. All of which come up very regularly. And they all have reasonably nice formulas that explain what they sum to. Let's begin with the simplest ones of arithmetic sums.
So there's an example. This supposedly is the kind of problem that was assigned to children in the the 18th century to keep them busy in class. And the great mathematician Gauss, Carl Friedrich Gauss, whom you know for magnetism and from probability theory, but also in fact the inventor of congruence and the number theory that we've studied, showed his brilliance as a child prodigy.
When he was nine-years old, supposedly, he noticed that in that short of numbers, that we just saw, there were 30 numbers, and each one was 13 greater than the previous one. The idea being that the tutor didn't want to go through the effort of summing everything up. He knew the trick to get the sum quickly, but he kept his students busy for hours doing that kind of problem.
I don't know whether that this is a true story or not, but it's a good story. So let's go on with it. So in other words, what Gauss noticed was that the numbers on that page looked like 89 and 89 plus 13 down through the 30th number 89 plus 29 times 13. And then he saw how to get the sum of a simple expression for the value of this sum.
And the logic is that let's call the first term F and then the next term is F plus 2 d-- F plus d, where d is 13 and F is 89. Next one would be F plus 2 d down to the end. And I'm going to call the last term L, which is 89 plus 29 times 13. And this would be L minus d or 89 plus 28 times 13. And let's call that sum A. We don't know what it is yet, but we're very quickly going to derive it.
One of the standard tricks to find nice formulas for sums is to find a arithmetic relation between the sum and a slight perturbation of the sum. In this case, I'm just going to write the sum backwards. So it's the same sum A, but written where the first term is last and the last term is first.
And now notice what happens when I add up these two sums. I get 2A of course. But every one of these terms-- this is a F plus L. This is a F plus d plus L minus D. It's F plus L. This last one is an F plus L.
Every one of these pairwise subsums comes out to be F plus L. And now we have a formula for the whole series in my simple formula that A is equal to the sum of the first term plus the last term divided by 2 times the number of terms. By the way, the first term plus the last term divided by 2 maybe is more memorable if you remember that it's the average term. It's the average size term times the number of terms. And that's how you sum up an arithmetic sum.
So we can wrap up with a familiar example, namely the sum of the integers from 1 to n. This is an arithmetic series, starts with one. And the d, that is the difference from successive terms is simply 1, 1 plus 1, 1 plus 1 plus 1 down to n. And according to our formula, it's the first plus the last over 2 times the number of terms. And we have that familiar formula for the sum of the first n integers.