When induction isn't enough. So sometimes
we have a problem where the statement
feels like it should be proved by induction, just
simple ordinary induction on the statement itself,
but sometimes it's maybe not so obvious
how to do this.
So it turns out…
maybe a little bit of a spoiler here
it turns out that weak induction, or the Principle of Mathematical Induction
and strong induction, which we'll see on the next slide,
it turns out they are equivalent. You can actually prove that they imply each other.
This proof is not easy - well
one direction is easy the other direction is actually a little bit tricky to word,
but it does emphasize that all things could be proved with weak induction
but just the statement that you have to prove is actually trickier.
In this case, anyways all that meta aside, let's look at this example.
So let x n be a sequence defined by x1 is 4,
x2 is 68, and xm is defined recursively as
2 times x m minus 1 plus 15 times x m minus 2,
for all m greater than or equal to 3, okay?
So this is what you call a recursive definition, or
recursive statement, all of these things.
Recursion statement, all of these things mean the same thing.
x m is defined in terms of previous terms.
So if I wanted to determine x3, I would plug in
I would plug in 3 into here, which would give me 2x2,
so it'll be 2 times 68, plus 15 times x sub
3 minus 1, so it's x sub 1, that's 4 so 15 times 4 which would be 60
and add the two together and get the number.
What are we going to prove? We're going to prove here that x n is equal to
2 times minus 3 to the n, plus 10, times 5 to the power of n minus 1.
And we're going to try to do this by induction, okay?
the base case for n equals 1,
we plug it in and we see that it works.
x1 is 4, 4 is the same as 2 times minus 3 plus 10.
And that's the formula.
The inductive hypothesis, we're going to assume that x k is equal to this
expression
and we're going to assume this is true for some k in the natural numbers.
Now for k plus 1, well what do we do? Well okay
we have x k plus 1...
and now...
we have a couple of problems here. We either have that k plus 1 is 2,
right, because again all we know is that
k is a natural number so k plus 1 is at least 2,
if k plus 1 is 2, then we'd have to do another case.
So we might need multiple base cases, it's something to think about.
But let's just assume that we could prove the
k equals 1 case… sorry the k plus 1 equals 2 case.
So let's assume that we can prove that P2 is true as well.
So take that for granted so that let’s assume that k plus 1 is at least 3.
We can use the
recursion statement, the recursive relation
between x k plus 1 and its previous terms.
So let's just suppose that this is true,
and even if this was true we can substitute x k for this value,
and we can expand, but the problem is we still have this x k minus 1 term.
And what's happening is that our induction hypothesis, or
inductive hypothesis is too weak.
It's not strong enough to give us the result that we want.
So in order to do this, we need…
well use one or two ways. One, we can reword
the statement that we're trying to prove, that's harder,
or the easier way is to use something called strong induction.
So that's what we're going to see now. The Principle of Strong Induction.
Again, this is an axiom. As I said this is equivalent to the
Principle of Mathematical Induction.
It's not so easy to prove, but you can do so.
It's also equivalent to the Well Ordering Principle which we
saw last week in last week's video.
That's an axiom I like a lot, I think it's pretty interesting
and has a lot of cool consequences. Same as induction,
but it's worded in a very easy way.
Anyways the Principle of Strong Induction. So if
or a sequence of statements P1, P2,
and so on and so forth, we have the following:
that P1 all the way up to P b are true
(“are” true? “Is” true?
Probably “is” true),
or some b inside the natural numbers,
and P1, P2 all the way up to Pk
are true implies that that Pk plus 1 is true
for all k inside the natural numbers,
then we know that Pn is true for all natural numbers n.
So what is this really saying? Okay so I can read a slide,
but what is this saying?
So what this is saying is, instead of assuming that just
Pk is true and proving that Pk plus 1 is true,
we're going to assume that all of the terms from P1 to…
all the statements from P1 to Pk are true.
So if we think about this in the domino analogy, it's no longer that
we're just assuming that the kth domino falls implies that the k plus first domino falls,
we're assuming that the first k dominoes have already fallen
and that that implies that the k plus first domino has fallen.
That's the idea behind the Principle of Strong Induction.
Now it turns out because you're proving multiple base cases possibly,
you can also take k to be at least b here.
So again b is just some natural number.
Again so in the Principal of Mathematical Induction, you always have b equals 1,
we only prove the first case and then the
second implication step, we have Pk implies Pk plus 1.
Here we have P1, P2 all the way up to Pk imply Pk plus 1.
Now typically you don't use all of the cases.
Sometimes it helps to know they're all true.
Sometimes you only need a couple of previous steps.
Either way is fine.
But that's the idea behind the Principle of Strong Induction.
Now if you want to see an example, I'm not going to do an example here
because they do take a decent amount of time
and they are quite convoluted,
but I do have other videos on the Math 135 Resources Page where
you can check out if you want to see an example of strong induction.
I also explain how to know when to use strong induction,
and when to use weak induction.
Pretty much I always start the proof by induction,
and if I get stuck or if I need multiple base cases or if I need to go back
a couple of steps before, instead of just k I need k minus 1 and k minus 2 being true,
something like that, then I'll go back and change my proof to be strong induction.
So I usually just leave a couple of blanks just in case I need to
prove something with strong induction.
Okay so that's the Principle of Strong Induction.
Maybe one last little topic here that fits in nicely,
the Fibonacci sequence. This is a beautiful sequence in mathematics
and we define it as follows: we let f1 equal 1, and f at 2 equal 1,
and we're going to define every term after that to be
the sum of the previous two terms.
So this defines the sequence
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on and so forth.
It's a cool sequence, it appears in lots of applications.
One of my favorite things to tell students is to go online and look up
a YouTube video by a band called Tool
and the song is called Lateralus
and it uses the Fibonacci sequence in a
really cool way. I think it's a really neat song,
and it's also a good song in its own right.
So check that out if you're interested in
music or if you want to see some cool applications of the Fibonacci sequence.
There are lots, that's just one of my favorites
that I'll mention to you.
Again this is one of these things you should just know.
You should know the Fibonacci sequence. Every term is defined as -
every term after the first two, which are both 1’s,
is defined as just the sum of the previous two terms. You should know the sequence.
We've seen a lot of - we’ve seen a couple of proofs in class
of induction statements that use the Fibonacci sequence.
Again, beautiful, beautiful..
it's just a beautiful topic. It's a beautiful sequence.