An induction proof

You may remember that I showed you this classical formula, Archimedes, for the sum of the first n squares. We’re now going to proceed to prove it by induction, by using the induction method, just for the joy of it. And also, perhaps, to illustrate the use of our arithmetical laws and fractions and this sort of thing. Remember how induction works? We have to prove the proposition P n for a certain n-bar that we’re free to choose. And then we have to prove that, subsequently, the truth of P n implies the truth of P n plus 1. Then it will follow that P n is true for all subsequent n.

So here’s our formula to prove, and the first step in the induction is to choose an n-bar and prove the formula for that value of n. I’m going to take n-bar equals 1. In that case, the left side of the formula reduces to 1 squared, and the right side of the formula can be calculated. I replace n by 1, and I get 1. Well, it’s true that 1 squared is equal 1. And therefore, the formula is true for n equals 1. First step. The next step in the proof is assuming that it is true for a certain given n, show that it then follows that the formula is true for n plus 1. Then, the proof will be complete.

Here’s how it works. This is a challenge proof, again. You don’t need to be able to follow this to continue in the course, but I would be impressed if you did. So here’s the left-hand side of P n plus 1. See, I’ve written the squares up to n plus 1. I claim that this is equal to this expression simply because we are assuming that P n is true. Why is that so? Well, because P n being true implies that the two quantities in the blue boxes are equal. And so we have the equality.

Now, the idea is to work on the right-hand side, the last expression we have here, to make it look like the right-hand side of P n plus 1. Let’s see how to do that. I’ve massaged the two terms a little bit. You see, in the first one, I’ve simply put the n in a different order in the multiplication by the associative law. That doesn’t change anything. And then the second term, I’ve written n plus 1 squared as n plus 1 times n plus 1. I’ve multiplied by 6, but I’ve also divided by 6, so I haven’t changed anything. However, that does reveal that the two terms have a common factor, namely n plus 1 over 6.

I factor it out, and in the braces, I have two terms. I’ve used here the distributive law that we saw. There it is. Now, the next step is to simplify the expression inside the braces by the distributive law and other arithmetic laws. You get it equal to 2n squared plus 7n plus 6. I leave you to check. And now, the next step is to realise that the quantity in the braces can be written as the product of n plus 2 and 2n plus 3. The procedure by which you decompose it this way is called factoring. It’s a very important process that we’ll be looking at carefully later on.

At the moment, you can at least check, by removing the parentheses, that this equality is true. Now, once you have that, the equality of these two, you can simply regroup the last expression. And you recognise that you have exactly the right-hand side of P n plus 1, because it’s the formula for P n but with n replaced by n plus 1. And so you have the equality affirmed, and that’s the end of the proof. Let us now take a look at a very useful notational device called sigma notation. It enables us to write sums in a nice compact way. Consider n real numbers– a1, a2, up to a n– and we wish to take their sum.

We can write the sum in the dot notation that I have used so far– a1 plus a2 and so forth, up to a n. But the sum can also be expressed in a compact form, sigma– that’s the Greek capital letter sigma– sum from i equals 1 to n of ai. That simply means the sum I’ve indicated on the left. Now, i is just a dummy variable in this notation. It has no life of its own. It’s just a placeholder. It indicates where the index is, and the index takes values between 1 and n.

So for example, if I were to write in the sigma notation the very same sum using the letter k as the index rather than the letter i, it has exactly the same meaning. It changes nothing. Now, if you look at the example that we were dealing with, this allows us, the sigma notation, to write the left-hand side in a more elegant way. In fact, we can write it this way. It’s a summation i squared, where i runs from 1 to n. Note here that we are summing functions of the index i in this sum. Functions are a very important topic which happen to be the next one on our agenda.