Hello everyone. Welcome to week 4 of Carmen's Core Concepts.
My name is Carmen Bruni, and in these videos, we talk about
the week's worth of materials in Math 135,
but we're going to go through this very quickly, so
again, this isn't meant to be a substitute for not going to lectures,
or not doing homework, or not actually trying problems, right?
These are just meant to
supplement the course and hopefully
help you if you missed something during the week,
or need a clarification on something.
Principle of Mathematical Induction, this is how we started our week.
So this is an axiom of mathematics.
If a sequence of statements P1, P2, P3 and so on,
satisfy that P1 is true,
and for any natural number k, if Pk is true
then, Pk plus 1 is true, then
Pn is true for all natural numbers n.
And the analogy to think about here is like a domino analogy, okay?
So here I don't have dominoes, I actually have little jewel cases
that I'm going to stack up,
and so the idea is if you have somehow…or if you have
infinitely many jewel cases, so I only have 3 here
but you can imagine that this goes on forever,
and the idea is that if P1 is true so this one…
so the idea is I want to knock them all down.
So if P1 is true, I can knock down the first one,
and for any k the natural numbers if the kth one gets knocked down,
then the next one gets knocked down, the k plus first one gets knocked down,
then all the dominoes will get knocked down, right?
That's the idea here, right? So if I push
the first one down, then it will knock the second, and the third, and the fourth
and so on, and that's how
the Principle Mathematical Induction works.
Once I know that the first one is true
and that the first one is true implies that the second one is true,
and the second one is true implies that the third one is true,
and the third one is true implies that the fourth one is true, and so on and so forth,
then as long as I can prove P1,
then all of them will fall.
So we gave a couple of examples of bad induction proofs in class.
Maybe I'll just mention what the sort of idea is here.
So here's an example where if I had the 2
over here and as you saw I knock them down
but they don't knock down the third one.
So here would be an example where P1 and P2 are true, but
P2 doesn't imply P3.
If I knock down P2, I don't knock down P3. It's too far away.
So the mathematical analogy is just that they don't imply each other
So that was similar to the horse one where we saw that P1 didn't imply P2
Again if you're looking for that horse example, it will be in lecture 16
on the Math 135 Resources Page.
Okay so that's the domino analogy. Again
so if I can show that the kth is true implies that the k plus first is true,
and k is an arbitrary natural number,
then I've shown that
all of them are true provided of course I can show that the first one is true.
Let's see an example.
So again the statement’s sort of one thing, and
actually proving things with Mathematical Induction feels like a different
sort of set of skills.
I usually find that students have trouble with the statement,
but have no problems actually proving things with Mathematical Induction.
So let's see an example:
so prove that…
okay so here we have our sum notation from the last week. Revisiting, that's
the sum from i equals 1 to n of i squared is equal to
n times n plus 1 times 2n plus 1 over 6.
So again what is this sum on the left mean?
And this is true… we're trying to prove this for all natural numbers n,
so we have infinitely many statements.
Now what does this sum mean? Well the sum is the sum
of all squared numbers from 1 to n.
So 1 squared, plus 2 squared, plus 3 squared plus, 4 squared, so 1 plus 4 plus 9
plus 16 and so on and so forth, okay?
All the way up to n squared.
We're trying to show that sum is equal to this nice closed form expression,
so the thing on the right is called a closed form expression.
In class we saw some examples… we saw one example in my class,
of how to actually determine the closed form expression.
It's one part, you know, guessing and one part perseverance, you know.
You just have to kind of try some numbers and hopefully see the pattern,
if you want to try to figure out the closed form without being given it.
How’s the proof… So how is the proof of this going to work?
We’re going to let Pn be the statement that the sum
is equal to the desired closed form formula,
and that this holds.
So we're going prove that Pn is true for all natural numbers
by the Principle of Mathematical Induction.
So step one is always the base case, okay?
So when n equals 1 this is the statement that we'd like to prove,
“The sum of the squares from 1 to 1
is equal to this expression on the right.”
Why does this hold, in this case? Well
the expression on the right is just 1 times 2 times 3 divided by 6.
Well that's 6 over 6 that's 1,
and this sum is just the sum from 1 up to 1 of i squared
so 1 squared and that's just 1.
So in the base case, it's very simple.
Usually base cases are easy.
If they're not, then you're probably missing something.
So that's the base case. So we've proved that P1 is true,
right, that was the first part of Mathematical Induction.
Now the second part is:
“If Pk is true, then Pk plus 1 is true.”
So how do we break that down? Well we have our hypothesis which is:
“Pk is true for some natural number k,”
and we'd like to show that Pk plus 1 is true given that we know that Pk is true.
So here we have our induction hypothesis then.
We're going to assume that Pk is true,
the key words here are “for some k in the natural numbers.”
So we don't know what k is, but we know it's a natural number
and it’s an arbitrary natural number.
Maybe it's a million, maybe it's 10 million, maybe it's a gagillion, whatever it is
it's some natural number, okay?
What does this mean? So what does Pk being true mean?
Well it means that the following statement holds:
that the sum of the numbers from 1 to k…
the sum of the squares of the numbers from 1 to k
is equal to k times k plus 1 times 2k plus 1 over 6.
That's our inductive hypothesis.
Now getting to the inductive step, or the inductive conclusion,
it's a…
it's involved okay, so the next slide is going to be a little bit involved.
There's just no way around it. Otherwise I'd have to
break it up, and I'd rather put it all on one page.
So this is something that I want you to remember.
Hopefully write down on a piece of paper or something,
pause the video and do that because we're gonna use it on the next slide.
The inductive step, so what are we doing in the inductive step?
Well we'd like to show that the sum of the squares from 1,
now this time to k plus 1
is equal to the formula, but instead of n I have k plus 1’s everywhere.
Now how do we do this? Well
what's the technique for these sums?
Usually…so it depends on what kind of sum you have.
Here we have a very simple sum where only the top index is changing.
So usually what will happen in this case is you'll just
pluck off the last term,
and you'll be left with a k term,
and this sum right here, this sum from i equals 1 to k,
that's reminiscent of the inductive hypothesis.
And that's the thing that we're going to substitute here, okay?
That's the main idea here. So we're going to take off…take the sum,
break off the last term, go from 1 to k
of i squared and we're going to get this equality.
Something to keep in mind…what do we need to keep in mind…
so sometimes it doesn't work out this nicely.
They sometimes both indices depend on k, it really does depend on the question,
and this the summation. So you have to pay attention as to where the
variable is in your question, where the indexing variable is.
There’s a difference between the variable n and the variable i here.
Make sure you understand that difference.
If not I suggest going back to CCC week 3 video.
We talk about that in there.
Okay assuming that all that is good,
we have now our sum from 1 to k and we took off the k plus 1 squared term,
now we're using the inductive hypothesis
that's what the “IH” over this equal signs mean.
You should state when you're using the inductive hypothesis,
that's very important. It's very important to let the reader know that
you know what you're doing. You're not just sort of symbol mashing.
You can also write down words “by the induction hypothesis”,
“by the inductive hypothesis”, that's fine as well.
Here I'm just going to put it as IH because clearly I'm running out of room on this slide.
So the sum of squares from 1 to k is
given by this expression, that was the inductive hypothesis,
and then plus k plus 1 squared.
When you get to this point, you have options.
Option 1 is to expand everything.
When you can avoid it, it's usually good to try to avoid it.
In this case, we can avoid it. We can actually factor. We have the k plus 1 term
that we can pull out, and this makes sense to do because we
also need a k plus 1 in our final answer, so
pulling out this k plus 1 factor should help us out a lot.
So pulling that out we have this left.
Find a common denominator, add the terms,
and now in the numerator, we have 2k squared plus 7 k plus 6.
Factor.
My favorite “F” word.
And that's it. So once we factored it, we have k plus 1,
k plus 2, and 2k plus 3 that's what's left.
Hence, the sum of squares is equal to what we expect.
Why is that true? Well that's true because of the Principle of Mathematical Induction,
right? We show that P1 is true and that Pk implied Pk plus 1.
Hence this is true for all natural numbers n.
And that's induction in three or four slides.
That's the main idea. Again we saw this all week. We
saw lots of examples, we saw examples using summations,
we saw examples… I did one using a chocolate bar,
we've done examples…
all kinds of examples.
Sequences, we'll get to sequences in a minute, but I mean
this is a concept that you really should understand,
and really make sure that you get solidly down.
It takes a while to write up and these arguments do take a little bit of time, but
once you get the hang of it, they're very quick.
And I like to call these “follow your nose” type of things,
right? You know that with the inductive step, you
need to get back to the inductive hypothesis, so make that appear.
Do a little bit of symbol rearranging,
expand or factor is usually the trick
and get the result you want.