Hello everyone. In this video, we're going to talk about the 2000 exam,
and we're going to start with question 3.
So let a sub 1 equal 2, a sub 2 equal 3,
and a sub n equal 3 times a sub n minus 1, minus 2 times a sub n minus 2,
for n greater than or equal to 3.
Show that a sub n is equal to 2 to the power of n minus 1 plus 1, for n greater than or equal to 1.
So when you see a question like this, it feels pretty natural to use some sort of induction.
Because I'm going back twice, I think
I'm going to use Strong Induction to prove this, and
especially since I have the condition for n greater than or equal to 3,
I definitely want at least two base cases
to account for this fact.
You'll see where all this comes into play when you write the proof,
but for now, let's just actually go through it.
So for n equals 1 and 2, we're just going to plug it in and
show that it works. So the base cases are actually pretty straightforward.
a sub 1 equals 2, and 2 is the same as 1 plus 1, which is the same as
2 to the power 1 minus 1 plus 1, so that's easy,
and a sub 2 is equal to 3. Well 3 is 2 plus 1,
and 2 is the same as 2 to the 2 minus 1 plus 1. So
the claim definitely holds for the first two values.
Now for the induction hypothesis, so because I'm using Strong Induction, I'm going to assume that
a sub i is equal to 2 to the power of i minus 1 plus 1
for all i between 1 and k, for some k in the natural numbers,
and I'm going to add the extra restriction that k is greater than or equal to 2.
Now why do I add this extra restriction k greater than or equal to 2?
That's going to come through in the induction conclusion, okay,
and the main reason for this is that I need to
be able to use the recurrence relation at some point,
which we'll see in a minute,
and to use the recurrence relation, I need that n is greater than or equal to 3.
So if I have k is greater than or equal to 2, then k plus 1
is greater than or equal to 3, and I can use the recurrence, okay?
That's why I need k is greater than or equal to 2.
So in the induction conclusion, now we're going to prove that a sub k plus 1
is equal to 2 to the power k plus 1.
So since k plus 1 is greater than or equal to 3,
I can use the recursive definition as given in the formula
because k plus 1 is large enough,
and my first step is valid, so a k plus 1 is equal to
3 a k minus 2 a sub k minus 1. So that's good.
Now from this point, I want to use the induction hypothesis, so this is why I needed
to go back in time twice so that I could use the a k definition
and the a k minus 1 definition. I think I need both of those.
Well I need both of those to make this question work,
so that's why I needed to have Strong Induction here.
So substitute a k with this, and substitute a k minus 1 with this,
and then once you do this, it's just a matter of expanding, which we do. So
3 times 2 to the k minus 1, 3 times 1 is 3,
minus 2 times 2 to the k minus 2, I add exponents,
so 1 plus k minus 2 is k minus 1.
Minus 2 times 1 is minus 2, so that's good.
3 minus 2 is 1, so that takes care of that. I have
3 times 2 to the k minus 1, minus one copy of 2 to the k minus 1, so it's like
3x minus x, so that's 2x, or 2 to the k minus 1,
or 2 times 2 to the k minus 1, and then if I multiply this together, add the exponents, and I get
2 to the k minus 1 that's - should be plus 1.
Sorry, let me fix that quickly.
So fix that, that's good.
Thus, the statement is true for n equals k plus 1,
and the claim is proven by the Principle of Strong Induction.
And that's it, okay? So just a quick recap.
So what's the recap going to say? Okay, so again,
Strong Induction, not weak induction because I need to go back twice.
So you might not see this until you actually write down the induction conclusion step,
but that's okay. If you notice a little late, just go back and correct it.
After using that and simplifying,
that part's easy.
So once you know to use Strong Induction, that's okay,
and I need two base cases so that I can ensure that k is at least 2.
So if I prove the first two base cases, then I can assume that k is at least 2 because I know that
when k is 1 and k is 2, I already have the claim, okay?
And that's it.
So hopefully that gives you a little bit of an idea how to do an induction question,
and good luck on the final.