PROFESSOR: So let's look at a last example of applying the well ordering principle, this time to something that we actually care about-- a theorem that really does require some--
The theorem is the following famous formula for the sum of a geometric sum-- for a geometric series or a geometric sum.
So the numbers on the left, the powers of r starting at 1, which is r to the 0 followed by r, which is r to the 1, followed by r squared, up through the nth powerful of r. You add all those numbers up and it turns out that there's a nice, simple, fixed formula that doesn't have those three dots in it that tells you exactly what the value of that sum is in the formula. As you can read is r to the n plus 1 minus 1 is the numerator and r minus 1 is the denominator. And the claim is that this identity holds for all non-negative integers n and for all real numbers r that aren't 1 because I don't want the denominator to be 0.
So how are we going to prove this? Well, I'm going to prove it by using the well ordering principle, and let's suppose that this identity didn't hold for some non-negative integer n. So we'll apply the well ordering principle and we'll let m be the smallest number n where this equality fails-- it becomes an inequality.
Now, what I know about m immediately is that this equality, if you look at it, when n is 0 the left-hand side comes down. It degenerates to just r to the 0, or 1. The right-hand side, if you check it, is r minus 1 over r minus 1, which is also 1.
So equality holds when n is 0, and that means that the least m for which equality doesn't hold has to be positive. So, what we know about the least number where this equality fails is that it's positive. And that means in particular since it's the least one [? word ?] fails, if you go down one to m minus 1, the equality holds. So we can assume that the sum of the first m powers of r, starting at 0 and ending at r to the m minus 1, is equal to the formula where you plug in m minus 1 for n and you get that formula on the right, which I'm not going to read to you.
Well, we can simplify it a little bit. If you look at the exponent, r to the m minus 1 plus 1 is after all just r to the m. So repeating what I've got is that the sum of those first powers of r up to m minus 1 we can assume is equal to the formula r to the m minus 1 divided by r minus 1 because m failed and this was the number one less where it had to succeed.
So now we take the obvious strategy. What I'm interested in is properties of the sum of the powers up to r to the m. Now, the left-hand side is the powers up to r to the m minus 1, so there's an obvious strategy for turning the left-hand side into what I'm interested in. Namely, let's add r to the m to both sides.
So the left-hand side becomes just the sum that I want and the right-hand side becomes this messy thing, r to the m minus 1 over r minus 1 plus r to the m.
Well, let's just simplify a little bit. Let's put r to the m over the denominator, r minus 1, which I do by multiplying it by r minus 1. And then it comes out to be r to the m plus 1 minus r to the m over r minus 1. And I collect terms and look what I got.
I've got the formula r to the m plus 1 minus 1 over r minus 1, which means that the identity that I was originally claiming, in fact, holds at m contradicting the assertion that it didn't hold at m. In other words, we've reached a contradiction assuming there was a least place were equality fails, that means there's no counter example and the equality holds for all non-negative integers n.
So here's the general organization of a well ordering proof which we've been using. Let's just summarize it into a kind of template for proving things.
So what you have in mind is that there's some property, P of n, of non-negative integers. And what you'd like to prove is that it holds for every non-negative integer. So for all n in non-negative integers, P of n holds. And we're going to try to prove this by the well ordering principle, which means that we're going to define the set of numbers for which P doesn't hold. That is, the set of counter examples, and call that C. So C is the set of non-negative integers for which not P of n holds.
Now, by the well ordering principle there's got to be a minimum element, call it m, that's in C. And at this point the job-- by assuming that m is the smallest counter example, we have to reach a contradiction somehow. Now, up to this second bullet it's the template, but the third bullet is where the real math starts and there isn't any template anymore. How you reach a contradiction is by reasoning about properties of P of n, and there's no simple recipe.
But the usual organization of the contradiction is one of two kinds. You find a counter example that's smaller than m-- you find a C that's in the set of counter examples and C is less than m that would be a contradiction because m is the smallest thing at C. Or you reach a contradiction by proving that P does hold for m, which means it's not a counter example. And those are the two standard ways to organize a well ordering proof.