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.