1
00:00:00,833 --> 00:00:03,800
Hello everyone. Welcome to week 
4 of Carmen's Core Concepts.

2
00:00:03,800 --> 00:00:06,533
My name is Carmen Bruni, and 
in these videos, we talk about

3
00:00:06,533 --> 00:00:09,266
the week's worth of 
materials in Math 135,

4
00:00:09,266 --> 00:00:11,766
but we're going to go 
through this very quickly, so

5
00:00:11,766 --> 00:00:15,133
again, this isn't meant to be a 
substitute for not going to lectures,

6
00:00:15,133 --> 00:00:18,100
or not doing homework, or not 
actually trying problems, right? 

7
00:00:18,100 --> 00:00:20,133
These are 
just meant to

8
00:00:20,133 --> 00:00:22,433
supplement the 
course and hopefully

9
00:00:22,433 --> 00:00:25,000
help you if you missed
something during the week,

10
00:00:25,000 --> 00:00:27,633
or need a clarification 
on something.

11
00:00:27,633 --> 00:00:30,266
Principle of Mathematical Induction, 
this is how we started our week.

12
00:00:30,266 --> 00:00:32,500
So this is an axiom 
of mathematics.

13
00:00:32,500 --> 00:00:36,266
If a sequence of statements
P1, P2, P3 and so on,

14
00:00:36,266 --> 00:00:38,800
satisfy that 
P1 is true,

15
00:00:38,800 --> 00:00:41,500
and for any natural 
number k, if Pk is true

16
00:00:41,500 --> 00:00:44,333
then, Pk plus 
1 is true, then

17
00:00:44,333 --> 00:00:47,100
Pn is true for all
natural numbers n.

18
00:00:47,100 --> 00:00:50,366
And the analogy to think about here 
is like a domino analogy, okay?

19
00:00:50,366 --> 00:00:53,900
So here I don't have dominoes, 
I actually have little jewel cases

20
00:00:53,900 --> 00:00:55,633
that I'm going 
to stack up,

21
00:00:55,633 --> 00:00:58,966
and so the idea is if you have 
somehow…or if you have

22
00:00:58,966 --> 00:01:01,300
infinitely many jewel cases, 
so I only have 3 here

23
00:01:01,300 --> 00:01:03,966
but you can imagine that
this goes on forever,

24
00:01:03,966 --> 00:01:07,033
and the idea is that if 
P1 is true so this one…

25
00:01:07,033 --> 00:01:09,166
so the idea is I want 
to knock them all down.

26
00:01:09,166 --> 00:01:12,000
So if P1 is true, I can 
knock down the first one,

27
00:01:12,000 --> 00:01:15,633
and for any k the natural numbers
if the kth one gets knocked down,

28
00:01:15,633 --> 00:01:18,900
then the next one gets knocked down,
the k plus first one gets knocked down,

29
00:01:18,900 --> 00:01:20,933
then all the dominoes will 
get knocked down, right?

30
00:01:20,933 --> 00:01:23,900
That's the idea here,
right? So if I push

31
00:01:23,900 --> 00:01:27,633
the first one down, then it will knock the 
second, and the third, and the fourth

32
00:01:27,633 --> 00:01:29,533
and so on, and
that's how

33
00:01:29,533 --> 00:01:32,066
the Principle Mathematical 
Induction works.

34
00:01:32,066 --> 00:01:33,800
Once I know that 
the first one is true

35
00:01:33,800 --> 00:01:36,000
and that the first one is true implies 
that the second one is true,

36
00:01:36,000 --> 00:01:38,366
and the second one is true 
implies that the third one is true,

37
00:01:38,366 --> 00:01:41,433
and the third one is true implies that the 
fourth one is true, and so on and so forth,

38
00:01:41,433 --> 00:01:43,266
then as long as 
I can prove P1,

39
00:01:43,266 --> 00:01:46,200
then all of 
them will fall.

40
00:01:46,200 --> 00:01:48,266


41
00:01:48,266 --> 00:01:51,200
So we gave a couple of examples
of bad induction proofs in class.

42
00:01:51,200 --> 00:01:53,600
Maybe I'll just mention what 
the sort of idea is here.

43
00:01:53,600 --> 00:01:56,800
So here's an example 
where if I had the 2

44
00:01:56,800 --> 00:01:59,133
over here and as you 
saw I knock them down

45
00:01:59,133 --> 00:02:00,833
but they don't knock
down the third one.

46
00:02:00,833 --> 00:02:03,466
So here would be an example 
where P1 and P2 are true, but

47
00:02:03,466 --> 00:02:05,266
P2 doesn't 
imply P3.

48
00:02:05,266 --> 00:02:08,600
If I knock down P2, I don't knock 
down P3. It's too far away.

49
00:02:08,600 --> 00:02:12,566
So the mathematical analogy is just 
that they don't imply each other

50
00:02:12,566 --> 00:02:16,566
So that was similar to the horse one 
where we saw that P1 didn't imply P2

51
00:02:16,566 --> 00:02:19,633
Again if you're looking for that horse 
example, it will be in lecture 16

52
00:02:19,633 --> 00:02:23,833
on the Math 135
Resources Page.

53
00:02:23,833 --> 00:02:25,733
Okay so that's the 
domino analogy. Again

54
00:02:25,733 --> 00:02:29,800
so if I can show that the kth is true 
implies that the k plus first is true,

55
00:02:29,800 --> 00:02:31,400
and k is an arbitrary 
natural number,

56
00:02:31,400 --> 00:02:33,333
then I've 
shown that

57
00:02:33,333 --> 00:02:36,800
all of them are true provided of course 
I can show that the first one is true.

58
00:02:36,800 --> 00:02:38,433
Let's see an
example.

59
00:02:38,433 --> 00:02:40,366
So again the statement’s 
sort of one thing, and

60
00:02:40,366 --> 00:02:43,200
actually proving things with Mathematical 
Induction feels like a different

61
00:02:43,200 --> 00:02:44,866
sort of set 
of skills.

62
00:02:44,866 --> 00:02:47,866
I usually find that students have 
trouble with the statement,

63
00:02:47,866 --> 00:02:51,633
but have no problems actually proving 
things with Mathematical Induction.

64
00:02:51,633 --> 00:02:53,633


65
00:02:53,633 --> 00:02:55,866
So let's see 
an example:

66
00:02:55,866 --> 00:02:57,733
so prove 
that…

67
00:02:57,733 --> 00:03:00,766
okay so here we have our sum notation 
from the last week. Revisiting, that's

68
00:03:00,766 --> 00:03:03,866
the sum from i equals 1 to 
n of i squared is equal to

69
00:03:03,866 --> 00:03:07,066
n times n plus 1 times 
2n plus 1 over 6.

70
00:03:07,066 --> 00:03:09,000
So again what is this 
sum on the left mean?

71
00:03:09,000 --> 00:03:11,800
And this is true… we're trying to 
prove this for all natural numbers n,

72
00:03:11,800 --> 00:03:14,466
so we have infinitely
many statements.

73
00:03:14,466 --> 00:03:17,033
Now what does this sum mean? 
Well the sum is the sum

74
00:03:17,033 --> 00:03:19,400
of all squared 
numbers from 1 to n.

75
00:03:19,400 --> 00:03:23,866
So 1 squared, plus 2 squared, plus 3 
squared plus, 4 squared, so 1 plus 4 plus 9

76
00:03:23,866 --> 00:03:26,533
plus 16 and so on 
and so forth, okay?

77
00:03:26,533 --> 00:03:28,100
All the way up 
to n squared.

78
00:03:28,100 --> 00:03:31,833
We're trying to show that sum is equal 
to this nice closed form expression,

79
00:03:31,833 --> 00:03:34,066
so the thing on the right is 
called a closed form expression.

80
00:03:34,066 --> 00:03:35,033


81
00:03:35,033 --> 00:03:37,966
In class we saw some examples…
we saw one example in my class,

82
00:03:37,966 --> 00:03:40,500
of how to actually determine 
the closed form expression.

83
00:03:40,500 --> 00:03:44,933
It's one part, you know, guessing and 
one part perseverance, you know.

84
00:03:44,933 --> 00:03:47,833
You just have to kind of try some
numbers and hopefully see the pattern,

85
00:03:47,833 --> 00:03:51,833
if you want to try to figure out the 
closed form without being given it.

86
00:03:51,833 --> 00:03:52,933


87
00:03:52,933 --> 00:03:55,533
How’s the proof… So how is 
the proof of this going to work?

88
00:03:55,533 --> 00:03:57,500
We’re going to let Pn be 
the statement that the sum

89
00:03:57,500 --> 00:04:00,333
is equal to the desired 
closed form formula,

90
00:04:00,333 --> 00:04:02,333
and that 
this holds.

91
00:04:02,333 --> 00:04:04,400
So we're going prove that Pn 
is true for all natural numbers

92
00:04:04,400 --> 00:04:06,133
by the Principle of 
Mathematical Induction.

93
00:04:06,133 --> 00:04:07,633


94
00:04:07,633 --> 00:04:10,133
So step one is always 
the base case, okay?

95
00:04:10,133 --> 00:04:13,000
So when n equals 1 this is the
statement that we'd like to prove,

96
00:04:13,000 --> 00:04:15,633
“The sum of the 
squares from 1 to 1

97
00:04:15,633 --> 00:04:19,333
is equal to this 
expression on the right.”

98
00:04:19,333 --> 00:04:21,600
Why does this hold, 
in this case? Well

99
00:04:21,600 --> 00:04:25,300
the expression on the right is just 
1 times 2 times 3 divided by 6. 

100
00:04:25,300 --> 00:04:27,633
Well that's 6
over 6 that's 1,

101
00:04:27,633 --> 00:04:31,066
and this sum is just the sum 
from 1 up to 1 of i squared

102
00:04:31,066 --> 00:04:33,633
so 1 squared 
and that's just 1.

103
00:04:33,633 --> 00:04:36,000
So in the base
case, it's very simple.

104
00:04:36,000 --> 00:04:39,133
Usually base
cases are easy.

105
00:04:39,133 --> 00:04:42,900
If they're not, then you're 
probably missing something.

106
00:04:42,900 --> 00:04:46,266
So that's the base case. So 
we've proved that P1 is true,

107
00:04:46,266 --> 00:04:48,600
right, that was the first part 
of Mathematical Induction. 

108
00:04:48,600 --> 00:04:50,766
Now the
second part is:

109
00:04:50,766 --> 00:04:54,300
“If Pk is true, then 
Pk plus 1 is true.” 

110
00:04:54,300 --> 00:04:57,000
So how do we break that down? Well 
we have our hypothesis which is:

111
00:04:57,000 --> 00:05:00,066
“Pk is true for some 
natural number k,”

112
00:05:00,066 --> 00:05:04,266
and we'd like to show that Pk plus 1 is 
true given that we know that Pk is true.

113
00:05:04,266 --> 00:05:05,266


114
00:05:05,266 --> 00:05:07,466
So here we have our 
induction hypothesis then.

115
00:05:07,466 --> 00:05:09,333
We're going to assume 
that Pk is true,

116
00:05:09,333 --> 00:05:12,233
the key words here are “for some 
k in the natural numbers.”

117
00:05:12,233 --> 00:05:13,566


118
00:05:13,566 --> 00:05:16,500
So we don't know what k is, but 
we know it's a natural number

119
00:05:16,500 --> 00:05:18,066
and it’s an arbitrary 
natural number. 

120
00:05:18,066 --> 00:05:21,500
Maybe it's a million, maybe it's 10 million, 
maybe it's a gagillion, whatever it is

121
00:05:21,500 --> 00:05:23,633
it's some natural 
number, okay?

122
00:05:23,633 --> 00:05:26,100
What does this mean? So what 
does Pk being true mean?

123
00:05:26,100 --> 00:05:27,900
Well it means that the 
following statement holds:

124
00:05:27,900 --> 00:05:30,200
that the sum of the 
numbers from 1 to k…

125
00:05:30,200 --> 00:05:32,400
the sum of the squares of 
the numbers from 1 to k

126
00:05:32,400 --> 00:05:35,066
is equal to k times k plus 1 
times 2k plus 1 over 6.

127
00:05:35,066 --> 00:05:38,366
That's our inductive 
hypothesis.

128
00:05:38,366 --> 00:05:40,933
Now getting to the inductive step, 
or the inductive conclusion,

129
00:05:40,933 --> 00:05:43,166
it's a…

130
00:05:43,166 --> 00:05:46,866
it's involved okay, so the next slide
is going to be a little bit involved.

131
00:05:46,866 --> 00:05:49,133
There's just no way around 
it. Otherwise I'd have to

132
00:05:49,133 --> 00:05:50,733
break it up, and I'd rather 
put it all on one page.

133
00:05:50,733 --> 00:05:52,200
So this is something that 
I want you to remember.

134
00:05:52,200 --> 00:05:53,900
Hopefully write down on a 
piece of paper or something,

135
00:05:53,900 --> 00:05:57,466
pause the video and do that because 
we're gonna use it on the next slide.

136
00:05:57,466 --> 00:05:58,866


137
00:05:58,866 --> 00:06:01,166
The inductive step, so what are 
we doing in the inductive step?

138
00:06:01,166 --> 00:06:04,433
Well we'd like to show that the 
sum of the squares from 1,

139
00:06:04,433 --> 00:06:06,900
now this time 
to k plus 1

140
00:06:06,900 --> 00:06:10,433
is equal to the formula, but instead 
of n I have k plus 1’s everywhere.

141
00:06:10,433 --> 00:06:11,633


142
00:06:11,633 --> 00:06:14,100
Now how do we 
do this? Well

143
00:06:14,100 --> 00:06:15,533


144
00:06:15,533 --> 00:06:16,866
what's the technique 
for these sums?

145
00:06:16,866 --> 00:06:19,333
Usually…so it depends on 
what kind of sum you have.

146
00:06:19,333 --> 00:06:22,433
Here we have a very simple sum 
where only the top index is changing.

147
00:06:22,433 --> 00:06:25,233
So usually what will happen 
in this case is you'll just

148
00:06:25,233 --> 00:06:26,800
pluck off the 
last term,

149
00:06:26,800 --> 00:06:28,466
and you'll be left 
with a k term,

150
00:06:28,466 --> 00:06:31,633
and this sum right here, this 
sum from i equals 1 to k,

151
00:06:31,633 --> 00:06:35,000
that's reminiscent of the 
inductive hypothesis.

152
00:06:35,000 --> 00:06:38,066
And that's the thing that we're 
going to substitute here, okay?

153
00:06:38,066 --> 00:06:40,966
That's the main idea here. So we're 
going to take off…take the sum,

154
00:06:40,966 --> 00:06:43,633
break off the last 
term, go from 1 to k

155
00:06:43,633 --> 00:06:47,966
of i squared and we're
going to get this equality.

156
00:06:47,966 --> 00:06:50,400
Something to keep in mind…what 
do we need to keep in mind… 

157
00:06:50,400 --> 00:06:52,166
so sometimes it doesn't 
work out this nicely.

158
00:06:52,166 --> 00:06:55,333
They sometimes both indices depend on 
k, it really does depend on the question,

159
00:06:55,333 --> 00:06:57,666
and this the summation. So you have 
to pay attention as to where the

160
00:06:57,666 --> 00:07:00,600
variable is in your question, 
where the indexing variable is.

161
00:07:00,600 --> 00:07:03,866
There’s a difference between the 
variable n and the variable i here.

162
00:07:03,866 --> 00:07:05,500
Make sure you
understand that difference.

163
00:07:05,500 --> 00:07:08,400
If not I suggest going back 
to CCC week 3 video.

164
00:07:08,400 --> 00:07:10,000
We talk about 
that in there. 

165
00:07:10,000 --> 00:07:10,800


166
00:07:10,800 --> 00:07:12,466
Okay assuming that 
all that is good,

167
00:07:12,466 --> 00:07:17,066
we have now our sum from 1 to k and 
we took off the k plus 1 squared term,

168
00:07:17,066 --> 00:07:19,600
now we're using the 
inductive hypothesis

169
00:07:19,600 --> 00:07:22,033
that's what the “IH” over 
this equal signs mean.

170
00:07:22,033 --> 00:07:24,766
You should state when you're 
using the inductive hypothesis,

171
00:07:24,766 --> 00:07:27,733
that's very important. It's very 
important to let the reader know that

172
00:07:27,733 --> 00:07:31,000
you know what you're doing. You're 
not just sort of symbol mashing.

173
00:07:31,000 --> 00:07:33,733
You can also write down words 
“by the induction hypothesis”,

174
00:07:33,733 --> 00:07:36,433
“by the inductive hypothesis”, 
that's fine as well.

175
00:07:36,433 --> 00:07:40,866
Here I'm just going to put it as IH because
clearly I'm running out of room on this slide.

176
00:07:40,866 --> 00:07:44,033
So the sum of squares 
from 1 to k is

177
00:07:44,033 --> 00:07:46,333
given by this expression, that 
was the inductive hypothesis,

178
00:07:46,333 --> 00:07:48,266
and then plus k 
plus 1 squared.

179
00:07:48,266 --> 00:07:48,900


180
00:07:48,900 --> 00:07:51,633
When you get to this 
point, you have options.

181
00:07:51,633 --> 00:07:52,333


182
00:07:52,333 --> 00:07:55,133
Option 1 is to 
expand everything.

183
00:07:55,133 --> 00:07:58,400
When you can avoid it, it's
usually good to try to avoid it.

184
00:07:58,400 --> 00:08:02,233
In this case, we can avoid it. We can 
actually factor. We have the k plus 1 term

185
00:08:02,233 --> 00:08:04,633
that we can pull out, and this 
makes sense to do because we

186
00:08:04,633 --> 00:08:06,966
also need a k plus 1 in 
our final answer, so

187
00:08:06,966 --> 00:08:09,633
pulling out this k plus 1 factor 
should help us out a lot.

188
00:08:09,633 --> 00:08:10,433


189
00:08:10,433 --> 00:08:13,200
So pulling that out 
we have this left.

190
00:08:13,200 --> 00:08:15,633
Find a common 
denominator, add the terms,

191
00:08:15,633 --> 00:08:16,600


192
00:08:16,600 --> 00:08:20,166
and now in the numerator, we 
have 2k squared plus 7 k plus 6. 

193
00:08:20,166 --> 00:08:21,766
Factor.

194
00:08:21,766 --> 00:08:22,433


195
00:08:22,433 --> 00:08:23,633
My favorite 
“F” word.

196
00:08:23,633 --> 00:08:24,866


197
00:08:24,866 --> 00:08:27,766
And that's it. So once we
factored it, we have k plus 1,

198
00:08:27,766 --> 00:08:31,033
k plus 2, and 2k plus 
3 that's what's left.

199
00:08:31,033 --> 00:08:34,233
Hence, the sum of squares 
is equal to what we expect.

200
00:08:34,233 --> 00:08:37,800
Why is that true? Well that's true because 
of the Principle of Mathematical Induction,

201
00:08:37,800 --> 00:08:42,066
right? We show that P1 is true 
and that Pk implied Pk plus 1.

202
00:08:42,066 --> 00:08:44,233
Hence this is true for 
all natural numbers n.

203
00:08:44,233 --> 00:08:45,366


204
00:08:45,366 --> 00:08:49,433
And that's induction
in three or four slides.

205
00:08:49,433 --> 00:08:51,600
That's the main idea. Again 
we saw this all week. We

206
00:08:51,600 --> 00:08:55,066
saw lots of examples, we saw 
examples using summations,

207
00:08:55,066 --> 00:08:57,966
we saw examples… I did 
one using a chocolate bar,

208
00:08:57,966 --> 00:08:59,900
we've done
examples… 

209
00:08:59,900 --> 00:09:01,566
all kinds 
of examples.

210
00:09:01,566 --> 00:09:02,566


211
00:09:02,566 --> 00:09:05,100
Sequences, we'll get to sequences 
in a minute, but I mean

212
00:09:05,100 --> 00:09:07,300
this is a concept that you 
really should understand,

213
00:09:07,300 --> 00:09:09,733
and really make sure 
that you get solidly down.

214
00:09:09,733 --> 00:09:11,466


215
00:09:11,466 --> 00:09:14,133
It takes a while to write up and these 
arguments do take a little bit of time, but

216
00:09:14,133 --> 00:09:16,166
once you get the hang 
of it, they're very quick.

217
00:09:16,166 --> 00:09:17,133


218
00:09:17,133 --> 00:09:19,633
And I like to call these “follow 
your nose” type of things,

219
00:09:19,633 --> 00:09:21,766
right? You know that with 
the inductive step, you

220
00:09:21,766 --> 00:09:26,100
need to get back to the inductive
hypothesis, so make that appear.

221
00:09:26,100 --> 00:09:27,633
Do a little bit of 
symbol rearranging,

222
00:09:27,633 --> 00:09:29,933
expand or factor 
is usually the trick

223
00:09:29,933 --> 00:09:31,666
and get the 
result you want.