Hello everyone. So in this example we're going to talk about an induction problem,
and this happened to be one example that
I skipped from class to leave as an exercise, but
I wanted to go over it in a video.
And if you've seen it already, then at least you're going to get a little bit of extra practice with
the argument. So
let f n be the Fibonacci sequence,
so the first two terms are 1 and every subsequent
term is the sum of the previous two, that's what this says mathematically.
now we're supposed to show that f n is bounded by
7/4 to the power of n for all natural numbers.
So we're trying to show that each Fibonacci number is bounded by 7 over 4, okay?
The tip-off here to sort of use induction here is that we're
trying to show some sentence is true for all natural numbers n,
and the sequence that we have is defined recursively.
So both of these things combined sort of suggest let's use Mathematical Induction.
Now the question is do I use Strong Mathematical Induction
or just the Principle of Mathematical Induction?
And that you sort of - well you can try to figure out before you write the proof,
but I like to figure it out as I write the proof and if I'm wrong
I just go back and modify everything to use the other one.
You can always use Strong Induction if you want
but, it might save you time to use just the Principle of Mathematical Induction.
They are equivalent of course,
but that is a non-trivial exercise.
Okay, so back to the question at hand. So if we're going to prove this by induction, we need three things:
we need a base case, an induction hypothesis, and then the inductive step. So
the induction step…so
So let's start with the base case.
So for n equals 1, we have that
f at 1 equals 1, which is less than
7 over 4.
Okay so for the base case, we have for n equals 1 we have that f at 1
equals [1] so let's edit that…
f at 1 equals 1 which is less than 7 over 4. Okay
so base case is easy.
Induction hypothesis,
so assume that
that f of k
is less than frac
7 over 4 to the power of k.
So our base case is done
and the induction hypothesis we're going to assume it's true for some k.
Now we're going to do the induction step.
So for k plus 1,
we have…
f at k plus 1…
Well...
okay this is what we'd like to write. So let's
start with what we have. So for k plus 1 we have what?
So for k plus 1 we have f at k plus 1 we want to write that this is equal to f at
k plus f at k minus 1.
Oh I guess maybe I should go back here, so assume that f k this and this for some -
I should be a little more precise in my induction hypothesis
So for what k? Well k has to be some natural number, okay, so the induction hypothesis, let's review that.
Assume that f k is less than 7 over 4 to the k for some k in the natural numbers.
Now for the induction step, we have…
we want to write this. We want to write f k plus 1 is equal to f k plus f k minus 1,
but this is valid only when
k
plus 1 is at least 3.
So this is only valid when k is at least 2.
So this is only valid when k is at least 2,
then we know we're going to need at least one more base case because I mean
here we only have that k is 1, so k could be 1
and this is f at 2 which is f at 1 plus f at 0 and that doesn't really make sense, okay?
So we're going to need to do at least one more base case, so let's add that in now.
So for n equals 2, watching all my typos,
we have that f 2 is also equal to 1 and that's clearly less than 49 over 16 and that's
7/4 squared.
Okay so now we have our two base cases, okay?
So now in our induction hypothesis, well we already know that
1 and 2 are true, so we can actually additionally suppose here
that k is greater than or equal to 2.
So now this step here, f k plus 1 is
equal to f k plus f k minus 1, well this is valid since now…
valid since k plus 1 is greater than or equal to 3.
Okay, so now we have this,
but now, as you've noticed, now we're going to have to try to use
just the fact that f k is bounded by 7/4,
and that's not enough. We also need that f k minus 1 is bounded by 7 over 4
if we're going to try to make any progress with this question.
So what do we do now? Well
now we know that we need to use Strong Induction, so we're going to go back to the top
and we're going to fix this up by using Strong Induction.
So we proceed by Strong Induction.
Now we know which one we're using, so let's add that into our solution.
Now our induction hypothesis is wrong,
so we need to…
so we need to account for the induction hypothesis.
So now we're going to assume that instead of
f k is less than 7 over 4 to the k,
we're going to assume that f i
is less than or equal to 7 over 4 to the i.
Now we're going to put for all 1 less than or equal to i less than or equal to k
for some k in the natural numbers and k greater than or equal to 2.
So now we're assuming this holds for all i between 1 and k,
okay, and we've already proven two base cases so
so there's no loss of generality in assuming that k is at least 2 here.
Okay, now let's go back to the induction step,
which iI will magically make reappear.
Now from here, what are we going to do? Well now we can use the induction hypothesis.
So the induction hypothesis says that this is less than…
So now for k plus 1, we have this thing, right? Now remember our goal,
what's our goal? So maybe I'll write down the goal, right?
So now we want to show that f k plus 1 is less than
7 over 4 to the power k plus 1, okay?
So now that we're at this step, right,
usually the tricks in induction are either, you know, add 0, add 1...
or sorry add 0, multiply by 1,
or factor/expand, okay? In this case, factoring seems like the most natural thing to do
since something is in common. So let's try to factor and see where that leads us.
k minus 1. So the smaller of the two terms is this 7/4 to the k minus 1.
And what are we left with? We’re going to be left with…
So I factor out this 7/4 to the k minus 1,
and that’s just 7/4 plus 1,
and what's that equal to?
So 7/4 plus 1 that’s 11/4 plus the first thing.
And so the second thing is
11 over 4.
Now we want to show that f k plus 1 is less than
7/4 to the k plus 1.
Here we only have a 7/4 to the k minus 1, so the
other 2 better come from this 11 quarters.
Now...
if this is going to work, then this should be less than 7/4 squared,
which we've already seen is 49 over 16.
So maybe now the question to ask yourself is 11…
over- so let's pull up the old paintbrush here.
So now the question that we're going to ask is, “Is
11 over
4 less than
49
over 16?"
Question mark.
And how do we do this? Well if we cross multiply, right, we see
that this is going to be true if and only if…
cross multiply we get 11 times 16 over 4, we’ll leave the 4 there,
so 16 the 4 will cancel.
So this is going to be true…
you know let's just write that down.
So 11 times 16
over 4
is less than 49.
And this is true if and only if…
so if we cancel out a 4 from the 16, then we’re going to get 44
is less than 49.
So these were all “if and only if’s” so you can go in either direction of this proof,
and so we actually have the thing that we want to be true.
Now you don't need to show this, so I'm not going to save this
beautiful masterpiece, but
let's now just write down the result that we now want…
which is that this is…oops…
strictly less than now
49 over 16.
That's equal to…
now it's just a matter of just crunching through, so let’s see the crunch.
Okay so
11 over 4 we just saw was less than 49 over 16,
that's 7 squared over 4 squared, so I can multiply the tops and bottoms and get
7 over 4 to the k plus 1, that's exactly what we wanted to show.
So thus,
thus, this holds
and hence the
the statement
is true for all n [in the natural numbers]
by Strong Induction.
I probably should capitalize theorems.
Okay so let's back up and just sort of summarize what we did.
So our statement that we were trying to show here.
The statement we were trying to show is that the nth Fibonacci numbers less than 7 quarters to the n.
We're going to proceed by Strong Induction, which we saw by trying to do the proof.
We need two base cases, again this was an artifact of the proof.
You could also kind of justify it by the fact that we had to go back two previous terms,
so you might want to use two base cases.
Base cases are very easy to show, just plug in
1 into both sides of the inequality
and show that it's correct,
or just start - well so really you should start from the left-hand side
and show that it's less than the right-hand side.
Or vice versa, but in this case
I want to go in this direction.
So for n equals 2, we have f 2 equals 1,
it's less than 49 under 16, that's 7 quarters squared.
Now assume this is true for all…
so now our induction hypothesis, we're going to assume the claim is true for all i
between 1 and k for some natural number k,
and we're going to make sure that k is also at least 2
since we have two base cases that's not a concern for us.
And the induction step we now want to show that f k plus 1 is less than 7 quarters to the k plus 1
So for k plus 1, we're just going to plug it in.
We're going to use the recursive definition which is valid since k plus 1 is at least 3.
Then we use the induction hypothesis,
or induction hypotheses,
to show that each of these terms is less than 7 quarters
to the k or k minus 1 respectively.
Factor, simplify,
11 quarters happens to be less than 49 over 16,
we saw that in the old paintbrush doodle.
49 over 16 is 7 squared 4 squared, and the reason why we
picked 49 over over 16 was so that we can get the extra two
values of 7 quarters that we needed.
Thus the induction step is true and hence the statement is true
for all natural numbers n by Strong Induction.
And that's what we wanted to show.
So hopefully this gives you a little bit of [an] idea of
when to Strong or Weak Induction, when to use…
how many base cases to use,
and how to go through the proof of such an example.
I apologize this video is very long, but
induction examples do take a little bit of time to explain and get used to
in the beginning. After a little bit of time
hopefully this kind of example will just be very routine for you,
but it will take a little bit of practice and effort to get to that point.
So thank you very much for listening and good luck.