1
00:00:00,000 --> 00:00:04,533
Hello everyone. In this video, we're 
going to talk about the 2000 exam,

2
00:00:04,533 --> 00:00:07,500
and we're going to start with question 3.

3
00:00:07,500 --> 00:00:10,233
So let a sub 1 equal 2, a sub 2 equal 3, 

4
00:00:10,233 --> 00:00:14,600
and a sub n equal 3 times a sub n 
minus 1, minus 2 times a sub n minus 2,

5
00:00:14,600 --> 00:00:16,333
for n greater than or equal to 3.

6
00:00:16,333 --> 00:00:21,700
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.

7
00:00:21,700 --> 00:00:25,766
So when you see a question like this, it feels 
pretty natural to use some sort of induction.

8
00:00:25,766 --> 00:00:28,100
Because I'm going back twice, I think

9
00:00:28,100 --> 00:00:30,400
I'm going to use Strong 
Induction to prove this, and

10
00:00:30,400 --> 00:00:32,700
especially since I have the condition 
for n greater than or equal to 3,

11
00:00:32,700 --> 00:00:35,166
I definitely want at least two base cases

12
00:00:35,166 --> 00:00:38,066
to account for this fact.

13
00:00:38,066 --> 00:00:40,300
You'll see where all this comes into
play when you write the proof,

14
00:00:40,300 --> 00:00:42,066
but for now, let's just actually go through it.

15
00:00:42,066 --> 00:00:45,033
So for n equals 1 and 2, we're 
just going to plug it in and

16
00:00:45,033 --> 00:00:48,200
show that it works. So the base cases 
are actually pretty straightforward.

17
00:00:48,200 --> 00:00:52,000
a sub 1 equals 2, and 2 is the same 
as 1 plus 1, which is the same as

18
00:00:52,000 --> 00:00:54,533
2 to the power 1 minus 1 plus 1, so that's easy,

19
00:00:54,533 --> 00:00:57,533
and a sub 2 is equal to 3. Well 3 is 2 plus 1,

20
00:00:57,533 --> 00:01:00,600
and 2 is the same as 2 to 
the 2 minus 1 plus 1. So

21
00:01:00,600 --> 00:01:03,733
the claim definitely holds for the first two values.

22
00:01:03,733 --> 00:01:05,233


23
00:01:05,233 --> 00:01:08,866
Now for the induction hypothesis, so because I'm 
using Strong Induction, I'm going to assume that

24
00:01:08,866 --> 00:01:12,100
a sub i is equal to 2 to the 
power of i minus 1 plus 1

25
00:01:12,100 --> 00:01:16,000
for all i between 1 and k, for
some k in the natural numbers,

26
00:01:16,000 --> 00:01:19,266
and I'm going to add the extra restriction 
that k is greater than or equal to 2.

27
00:01:19,266 --> 00:01:22,933
Now why do I add this extra restriction 
k greater than or equal to 2? 

28
00:01:22,933 --> 00:01:26,166
That's going to come through 
in the induction conclusion, okay,

29
00:01:26,166 --> 00:01:28,433
and the main reason for this is that I need to

30
00:01:28,433 --> 00:01:31,466
be able to use the recurrence
relation at some point,

31
00:01:31,466 --> 00:01:32,700
which we'll see in a minute,

32
00:01:32,700 --> 00:01:36,500
and to use the recurrence relation, I need 
that n is greater than or equal to 3.

33
00:01:36,500 --> 00:01:39,300
So if I have k is greater than 
or equal to 2, then k plus 1

34
00:01:39,300 --> 00:01:42,900
is greater than or equal to 3, and 
I can use the recurrence, okay? 

35
00:01:42,900 --> 00:01:45,433
That's why I need k is
greater than or equal to 2.

36
00:01:45,433 --> 00:01:48,066
So in the induction conclusion, now 
we're going to prove that a sub k plus 1

37
00:01:48,066 --> 00:01:50,100
is equal to 2 to the power k plus 1.

38
00:01:50,100 --> 00:01:52,000
So since k plus 1 is 
greater than or equal to 3,

39
00:01:52,000 --> 00:01:54,800
I can use the recursive definition 
as given in the formula

40
00:01:54,800 --> 00:01:57,066
because k plus 1 is large enough,

41
00:01:57,066 --> 00:01:59,666
and my first step is valid, 
so a k plus 1 is equal to

42
00:01:59,666 --> 00:02:04,633
3 a k minus 2 a sub k 
minus 1. So that's good. 

43
00:02:04,633 --> 00:02:08,966
Now from this point, I want to use the 
induction hypothesis, so this is why I needed

44
00:02:08,966 --> 00:02:11,633
to go back in time twice so that 
I could use the a k definition

45
00:02:11,633 --> 00:02:14,766
and the a k minus 1 definition. 
I think I need both of those. 

46
00:02:14,766 --> 00:02:16,266


47
00:02:16,266 --> 00:02:18,266
Well I need both of those to 
make this question work,

48
00:02:18,266 --> 00:02:21,333
so that's why I needed to 
have Strong Induction here.

49
00:02:21,333 --> 00:02:24,800
So substitute a k with this, and 
substitute a k minus 1 with this,

50
00:02:24,800 --> 00:02:26,466


51
00:02:26,466 --> 00:02:29,233
and then once you do this, it's just a 
matter of expanding, which we do. So

52
00:02:29,233 --> 00:02:32,366
3 times 2 to the k minus 1, 3 times 1 is 3,

53
00:02:32,366 --> 00:02:35,433
minus 2 times 2 to the k 
minus 2, I add exponents,

54
00:02:35,433 --> 00:02:38,033
so 1 plus k minus 2 is k minus 1.

55
00:02:38,033 --> 00:02:41,066
Minus 2 times 1 is minus 2, so that's good.

56
00:02:41,066 --> 00:02:43,433
3 minus 2 is 1, so that 
takes care of that. I have

57
00:02:43,433 --> 00:02:47,866
3 times 2 to the k minus 1, minus one
copy of 2 to the k minus 1, so it's like

58
00:02:47,866 --> 00:02:52,500
3x minus x, so that's 2x, 
or 2 to the k minus 1, 

59
00:02:52,500 --> 00:02:56,100
or 2 times 2 to the k minus 1, and then if I multiply 
this together, add the exponents, and I get

60
00:02:56,100 --> 00:02:58,933
2 to the k minus 1 that's - should be plus 1.

61
00:02:58,933 --> 00:03:01,133
Sorry, let me fix that quickly.

62
00:03:01,133 --> 00:03:04,600


63
00:03:04,600 --> 00:03:06,933
So fix that, that's good.

64
00:03:06,933 --> 00:03:09,666
Thus, the statement is true 
for n equals k plus 1,

65
00:03:09,666 --> 00:03:13,133
and the claim is proven by 
the Principle of Strong Induction.

66
00:03:13,133 --> 00:03:15,466


67
00:03:15,466 --> 00:03:19,300
And that's it, okay? So just a quick recap.

68
00:03:19,300 --> 00:03:21,500


69
00:03:21,500 --> 00:03:23,300
So what's the recap going 
to say? Okay, so again,

70
00:03:23,300 --> 00:03:26,233
Strong Induction, not weak induction 
because I need to go back twice.

71
00:03:26,233 --> 00:03:29,066
So you might not see this until you actually 
write down the induction conclusion step,

72
00:03:29,066 --> 00:03:33,600
but that's okay. If you notice a little 
late, just go back and correct it.

73
00:03:33,600 --> 00:03:36,366
After using that and simplifying,

74
00:03:36,366 --> 00:03:38,333
that part's easy.

75
00:03:38,333 --> 00:03:40,200
So once you know to use 
Strong Induction, that's okay,

76
00:03:40,200 --> 00:03:43,166
and I need two base cases so that 
I can ensure that k is at least 2.

77
00:03:43,166 --> 00:03:47,133
So if I prove the first two base cases, then I can 
assume that k is at least 2 because I know that 

78
00:03:47,133 --> 00:03:50,566
when k is 1 and k is 2, I
already have the claim, okay?

79
00:03:50,566 --> 00:03:51,866


80
00:03:51,866 --> 00:03:54,133
And that's it.

81
00:03:54,133 --> 00:03:57,600
So hopefully that gives you a little bit of 
an idea how to do an induction question,

82
00:03:57,600 --> 00:03:59,733
and good luck on the final.