WEBVTT
1
00:00:00.000 --> 00:00:06.800
Programs okay so in that problem set there's an analogy that I'll do in a more simple way here in the board
2
00:00:06.800 --> 00:00:11.900
That's done in a lot of different books you can find and and you'll get the idea of this Conan drone
3
00:00:12.240 --> 00:00:20.480
So there's a town I always think of the old anti-grifit show because there's that guy Floyd the barber and everybody hangs out in Floyd shop and and
4
00:00:21.360 --> 00:00:23.360
And here's the deal
5
00:00:23.360 --> 00:00:27.000
In this town the barber shaves everybody that doesn't shave themselves
6
00:00:27.000 --> 00:00:32.720
Okay, everybody got that the fairly simple idea if you shave yourself you stay at home
7
00:00:32.720 --> 00:00:39.600
If you don't shave yourself you go to Floyd. There's one barber in town. I'm talking everybody
8
00:00:41.360 --> 00:00:43.360
Floyd's got a nice job
9
00:00:47.400 --> 00:00:51.200
Alternatively the town's all men, but we want to keep it interesting
10
00:00:51.200 --> 00:00:58.280
Okay, so if you don't shave yourself you got a Floyd so the question is does Floyd shave himself or not?
11
00:01:00.200 --> 00:01:02.200
Floyd's a male
12
00:01:03.480 --> 00:01:06.400
Well, I got the int- well, let's not go down this road. Yeah
13
00:01:08.280 --> 00:01:13.040
Does Floyd shave himself or not if you shave yourself are you supposed to go to Floyd?
14
00:01:14.320 --> 00:01:16.320
No, so Floyd shaves himself
15
00:01:17.160 --> 00:01:19.160
He's not supposed to shave himself
16
00:01:19.160 --> 00:01:21.160
That that
17
00:01:21.160 --> 00:01:23.800
Possibility doesn't work out, but if he doesn't shave himself what's he supposed to do?
18
00:01:24.080 --> 00:01:27.120
He's supposed to go to the town barber namely himself to shave himself
19
00:01:27.520 --> 00:01:29.960
So you can't answer that question does Floyd shave himself?
20
00:01:30.960 --> 00:01:34.840
If you say the answer is yes, the answer should be no if you say the answer is no the answer should be yes
21
00:01:35.000 --> 00:01:39.520
So this implies that the statement that I made at the beginning doesn't make any sense
22
00:01:40.240 --> 00:01:42.160
Right, that's a strange little Conan drone
23
00:01:42.160 --> 00:01:47.000
It seems like one of these stupid little puzzles somebody throws it's in a bar and you just say please go away from me
24
00:01:47.000 --> 00:01:49.000
I'm meeting a friend right it's like
25
00:01:49.520 --> 00:01:54.520
Or can I buy you another drink here, but but it's actually at the heart of
26
00:01:56.360 --> 00:02:01.480
Maybe the most important theorem and in about in theory of computation that there are programs that you can't
27
00:02:02.160 --> 00:02:08.320
But you can't write programs that things you want to compute that there are no programs for and I'm gonna get back to the example
28
00:02:08.320 --> 00:02:13.520
I did yesterday, but this time we're gonna nail it down in a relatively more rigorous way. So let's say
29
00:02:13.520 --> 00:02:20.160
Because what I want to do I want to convince you that there's no program that will find infinite loops and other people's programs
30
00:02:20.360 --> 00:02:23.960
Remember I mentioned that there's no such program that doesn't I'm gonna convince you of this today and it
31
00:02:24.280 --> 00:02:26.280
We'll bear a little bit down on that
32
00:02:26.280 --> 00:02:29.240
Barber analogy, but we're gonna see it in the diagonalization way
33
00:02:29.240 --> 00:02:33.080
You'll see it in your piece set with a barber analogy, but we're gonna see it here in diagonalization
34
00:02:33.520 --> 00:02:39.960
So so I tell Donna Donna when you go home tonight doing a big favor and for homework when you're all done with a problem
35
00:02:39.960 --> 00:02:48.080
Sick because I know you know you'll have plenty of extra time. Why don't you go ahead and write me a program that finds infinite loops and other people's programs and bring it in tomorrow
36
00:02:48.760 --> 00:02:52.680
Right and she likes a challenge so she comes in and she goes I have it here
37
00:02:52.680 --> 00:02:55.160
It isn't she gives it to me. So we're gonna assume now
38
00:02:55.560 --> 00:02:59.960
Proof by contradiction. We're gonna assume now that she's done it that she's come up with such a program
39
00:02:59.960 --> 00:03:01.960
And I'm gonna convince you that she's lying
40
00:03:02.520 --> 00:03:05.840
Okay, is everybody with me? All right, so here's oh
41
00:03:05.840 --> 00:03:07.840
Oh
42
00:03:08.040 --> 00:03:10.040
Well, there's a contradiction
43
00:03:15.960 --> 00:03:20.400
All right yesterday we talked about a table where I number all the programs in the whole world
44
00:03:20.400 --> 00:03:26.360
You know that answer yes or no to their inputs and I put them here and I number them one two three all the way up to infinity
45
00:03:26.360 --> 00:03:31.680
There they are every single program in the world no programs are missing. They're all there
46
00:03:32.200 --> 00:03:34.200
Okay, there's no program that's missing
47
00:03:34.200 --> 00:03:39.120
All the programs are there there may be things we want to compute
48
00:03:39.680 --> 00:03:46.440
That there are no programs for but we'll find that out later right now all the programs are listed here and we list them up here as well
49
00:03:47.440 --> 00:03:55.880
And we fill in this chart in the following way we run this program on this input on this program as input and we see whether it says yes or no
50
00:03:55.880 --> 00:04:00.600
Now yesterday we had a little bit of a fudge factor the question was well how do you know if it says yes or no?
51
00:04:00.600 --> 00:04:05.920
Right, maybe it does and I said well you could always check if it says yes because you could dovetail the computation
52
00:04:05.920 --> 00:04:11.000
But then the issue is well if it never says yes, they'll just be question marks and and we kind of got stuck
53
00:04:11.000 --> 00:04:15.160
And I said then I don't worry. You'll see it again, and I said well, you know, they're just gonna worry and let me show it
54
00:04:15.160 --> 00:04:17.160
Let me show you what really happens
55
00:04:17.280 --> 00:04:20.200
Today we have Donas program right nobody worried
56
00:04:20.200 --> 00:04:28.440
Today we have Donas program Donas program will tell us whether a program goes into an infinite loop or not so here's
57
00:04:31.640 --> 00:04:37.000
When they do is say yes or no to a given program like a compiler. Yes, this is good. No, it's not good
58
00:04:37.640 --> 00:04:43.560
Okay, so her program is one of those should be right right her program's one of those right her programs here
59
00:04:43.560 --> 00:04:51.320
V for Donna Donna's program is here. That's a good point Chris is right Donas programs in this list it takes programs and it says yes
60
00:04:51.320 --> 00:04:53.640
Do they have infinite loops or no they don't have infinite loops?
61
00:04:54.840 --> 00:04:57.920
Okay, by the way, we hope Donas program run on Donna
62
00:04:59.880 --> 00:05:02.200
Better tell us that it has no infinite loop right?
63
00:05:02.800 --> 00:05:05.720
I hope so right otherwise your program is below me
64
00:05:06.120 --> 00:05:08.440
So we know there's a one there. Yeah
65
00:05:08.440 --> 00:05:14.720
So when you run a program program for determining is if that program with any other program
66
00:05:18.160 --> 00:05:22.840
When I run Donas program on another program right it's telling me does it ever go into an infinite loop
67
00:05:23.760 --> 00:05:29.440
Right, right does it sometimes go into well no, well, I'm sorry Rob her program will take
68
00:05:31.600 --> 00:05:37.600
Her program will take the program and any input at all you want and tell you whether it whether it goes into an infinite loop
69
00:05:37.600 --> 00:05:43.640
It'll take two inputs your program right so I guess it but we can we but we can make Don it
70
00:05:43.640 --> 00:05:45.440
We can make a version of Donas program in here
71
00:05:45.440 --> 00:05:50.440
We can make Donas program just check if a program accepts itself or not and then Donas program would be in our list
72
00:05:51.320 --> 00:05:54.440
Okay, so so some version of Donas program is in here
73
00:05:55.560 --> 00:05:59.600
And that's not the main part of this idea so but let's continue all right
74
00:05:59.600 --> 00:06:03.440
So here's this list. Let's start filling it up with the help of Donas program
75
00:06:03.440 --> 00:06:08.440
Well, we'll take program one run it on itself Donas program says this is not an infinite loop
76
00:06:08.440 --> 00:06:13.920
So we let it run for a few years and sooner or later it says yes or no, I accept or I don't if it says I accept
77
00:06:13.920 --> 00:06:17.680
I'll put a one here if it says I don't I'll put a zero so let's say it doesn't accept it
78
00:06:17.680 --> 00:06:22.040
It says no, I say zero. It says yes to two now what happens here?
79
00:06:22.040 --> 00:06:26.120
I throw in program one on input three and Donas program say hey, this is going to be an infinite loop
80
00:06:26.120 --> 00:06:28.600
So what should I put in I want to re zero? We
81
00:06:28.600 --> 00:06:34.160
Just the choice and we're gonna do zero if it says no, we're gonna do zero if it's an infinite loop
82
00:06:34.160 --> 00:06:36.640
We're gonna do zero, but if it says yes, we're gonna put in one
83
00:06:37.120 --> 00:06:43.360
Okay, we're not gonna distinguish between infinite loops and saying no infinite loops and saying no are both gonna turn out to be zero
84
00:06:43.880 --> 00:06:46.960
All right, so in this way I fill in this whole table
85
00:06:46.960 --> 00:06:58.600
I can fill it all in as long as I go
86
00:07:07.360 --> 00:07:11.720
Her program does it that's our assumption I sent her home last night with this with this job
87
00:07:11.720 --> 00:07:16.280
I'm gonna convince you she's lying, but but she says she's got one that does it
88
00:07:16.600 --> 00:07:19.600
Okay, so first we run per program on everything determine whether
89
00:07:20.800 --> 00:07:22.800
And then we fill in these these values
90
00:07:25.120 --> 00:07:29.960
Right but the ones that do we just write zeros it okay question so far
91
00:07:30.960 --> 00:07:32.960
Everybody okay
92
00:07:33.160 --> 00:07:35.160
All right
93
00:07:35.280 --> 00:07:36.800
Right
94
00:07:36.800 --> 00:07:42.000
Here's the next step the next step is what we did yesterday you've seen this before I am now gonna go down the diagonal
95
00:07:42.000 --> 00:07:46.440
And I'm gonna convince you that there's a row in this table that you missed
96
00:07:47.200 --> 00:07:53.000
That there's a missing program here, but this time I want to analyze what that program is actually doing
97
00:07:53.680 --> 00:07:55.680
Here's the missing program
98
00:07:57.840 --> 00:08:01.720
I'm gonna go down this diagonal and I'm going to toggle all the bits
99
00:08:01.720 --> 00:08:07.280
So here's what I get I get one one one one zero
100
00:08:09.800 --> 00:08:15.520
This row could not possibly be in my infinite list if it wasn't my infinite list
101
00:08:17.880 --> 00:08:19.880
What would happen
102
00:08:20.560 --> 00:08:26.920
Right it would not agree with the if it was saying the 15th row it wouldn't agree with the 15th spot in that row
103
00:08:26.920 --> 00:08:32.800
This particular value that I just created is different than every single row that's already in the table
104
00:08:32.800 --> 00:08:37.080
It's different from the third row in the third spot. It's different from the 80th row in the 80th spot
105
00:08:37.080 --> 00:08:40.440
So this is a new row that was not included in our list of programs
106
00:08:40.520 --> 00:08:45.680
This is a computation that we have no program for what is this computation doing?
107
00:08:46.080 --> 00:08:52.440
What does this program if I could write it if it existed what would it accept?
108
00:08:53.200 --> 00:08:55.200
What are these ones representing?
109
00:08:55.200 --> 00:08:57.200
They were the old zeros right?
110
00:08:58.080 --> 00:09:00.920
This program accepts all things that either say no
111
00:09:03.600 --> 00:09:05.600
To these inputs or else
112
00:09:06.200 --> 00:09:09.960
Our infinite loops to these inputs right that's what this program does and
113
00:09:10.680 --> 00:09:13.440
This program doesn't exist that it wasn't in our list
114
00:09:13.760 --> 00:09:17.640
But I'm gonna convince this program everybody agrees now doesn't exist it wasn't in our list
115
00:09:17.800 --> 00:09:22.400
But what would it do if it did exist? It would say yes to every single
116
00:09:22.400 --> 00:09:25.760
Computation that ends up
117
00:09:26.720 --> 00:09:31.240
Saying no to that value or going into an infinite loop now that we agree this doesn't exist
118
00:09:31.240 --> 00:09:35.480
I'm gonna convince you that Dom is assignment last night implies that this does exist
119
00:09:36.240 --> 00:09:38.600
Donna has something that checks for infinite loops
120
00:09:39.240 --> 00:09:44.000
Right she can take any program and any input and check if there's an infinite loop
121
00:09:44.240 --> 00:09:48.680
Well, I could just take her program and fiddle with it a little bit and make a program that does this
122
00:09:48.680 --> 00:09:52.400
Here's what I do I take her program it checks for infinite loops
123
00:09:52.400 --> 00:09:56.920
I'd run this particular program on a particular input if it was an infinite loop
124
00:09:56.920 --> 00:09:59.840
I put a one there if it's not an infinite loop I
125
00:10:00.400 --> 00:10:05.960
Just run the program until it sooner or later tells me yes or no and then I know what to put in the next spot
126
00:10:05.960 --> 00:10:10.080
I could compute this line if Donna's program worked I
127
00:10:11.240 --> 00:10:15.160
Wouldn't have any trouble writing this program, but this program doesn't exist
128
00:10:15.160 --> 00:10:19.600
There is no way to write this program. It doesn't exist here
129
00:10:19.600 --> 00:10:26.440
So the fact that Donna said she had a solution has got to be wrong because if she has a solution I can write that program
130
00:10:27.520 --> 00:10:31.320
Right, this is a very subtle tricky idea. This is actually completely
131
00:10:31.840 --> 00:10:37.840
Relatively rigorous way of showing it you need to let it sink in a little bit. Here's the more moral of the whole thing
132
00:10:37.840 --> 00:10:41.680
If you try to write a program that accepts all other programs which
133
00:10:41.680 --> 00:10:46.640
Say no to themselves or infinite loop that's impossible
134
00:10:47.880 --> 00:10:53.680
You can't write a program that takes another program and an input and tells you whether it's an infinite loop or says no
135
00:10:53.920 --> 00:10:55.920
You can't write a program that does self-hating
136
00:10:56.960 --> 00:10:59.800
Right programs are not smart enough to know about themselves
137
00:11:00.760 --> 00:11:04.480
There's not enough to know about a lot of other programs, but if you include themselves in the group
138
00:11:05.240 --> 00:11:07.000
They lose their power
139
00:11:07.000 --> 00:11:13.160
Fly can shave everybody in town that doesn't shave himself, but if you include him in the town he loses his great perspective
140
00:11:14.040 --> 00:11:16.040
Right, so this analogy
141
00:11:26.040 --> 00:11:31.400
Because if you think of what this line actually is it's all the programs that
142
00:11:31.400 --> 00:11:37.520
That infinite loop on themselves or don't accept themselves. Why is that?
143
00:11:39.160 --> 00:11:45.360
Program one on itself either infinite loops or doesn't accept itself. So I put a one here program two on itself
144
00:11:45.360 --> 00:11:51.160
Either infinite loops or doesn't accept itself. So I put a one here program five on itself does accept itself
145
00:11:51.160 --> 00:11:53.160
So I put a zero here this
146
00:11:53.720 --> 00:12:00.320
Computation is trying to figure out which programs infinite loop on themselves and which or and which ones or which ones
147
00:12:00.320 --> 00:12:05.440
Don't accept themselves. This is a computation of all self-hating or infinite looping programs
148
00:12:05.920 --> 00:12:07.920
Do you see where the self thing comes in?
149
00:12:08.480 --> 00:12:13.920
Okay, so if Donna's program actually works I could build something that does this I take Donna's program
150
00:12:13.920 --> 00:12:20.720
I put a program into it. I run it on itself. She tells me if there's an infinite loop if there is I put a one here
151
00:12:21.080 --> 00:12:26.800
If there's not an infinite loop I just run the program on itself until I get an answer and if it says no
152
00:12:26.800 --> 00:12:32.280
Then I put a one there if it says yes, then I put a zero there. So I could use Donna's program to construct this even though
153
00:12:32.280 --> 00:12:36.480
We know that this particular program is impossible because it's not in our last. Yeah
154
00:12:46.480 --> 00:12:51.000
Like if maybe that's a that's a good question. What if I just took this horizontal
155
00:12:51.000 --> 00:12:53.880
And I made and I toggled all these bits
156
00:12:53.880 --> 00:12:57.880
And I tried to claim to you that road does not exist here
157
00:12:59.760 --> 00:13:02.840
Well, if you toggle one of them it just means that it's different from this row
158
00:13:03.040 --> 00:13:08.120
But it might be identical to one of the other rows. There's no guarantee it might not be somewhere else in our list
159
00:13:12.840 --> 00:13:14.840
Here here's one that is identical
160
00:13:19.560 --> 00:13:21.560
It's identical except for the first one
161
00:13:21.560 --> 00:13:23.560
Right?
162
00:13:24.560 --> 00:13:28.120
So if you're just so this one is different from that one, right?
163
00:13:29.160 --> 00:13:33.200
But now I'll have another one down here which is
164
00:13:41.240 --> 00:13:45.160
Say this well the same one this could have been here
165
00:13:45.160 --> 00:13:52.040
You're if you just concentrate on one row and you create this say I just changed the first bit of that row
166
00:13:52.080 --> 00:13:54.080
So I get this new
167
00:13:54.080 --> 00:13:58.920
computation and you're trying to convince me this row is not anywhere else in the whole
168
00:14:00.080 --> 00:14:03.520
But here it is. I just showed you it was number six. I just didn't write it in before
169
00:14:05.080 --> 00:14:09.320
The the idea of this diagonal argument is that there's no row that could ever be further on
170
00:14:09.320 --> 00:14:15.680
All right, well, so I'll take the I'll switch the whole thing good. That's the next step
171
00:14:16.240 --> 00:14:21.000
So how come how come I can't play this game with a diagonal idea right? It seems like I'm just cheating here
172
00:14:21.000 --> 00:14:26.240
Right you say it's not there because it's different than that when I say it is there. It's number eight. You just didn't see it
173
00:14:26.240 --> 00:14:40.360
So how come if I go down the diagonal it can't be number eight. Well, how do I know that? It's not a row. I can't see that as a bottom anyway
174
00:14:40.360 --> 00:14:47.640
This row number eight is going to be different at that spot
175
00:14:49.160 --> 00:14:51.160
So I know that that it couldn't have been there
176
00:14:51.160 --> 00:14:58.160
It's almost like my definition of projecting in your beauty. We are look if you're sense of this proof is that it's tricky and
177
00:14:58.480 --> 00:15:04.760
Magical it is it is a tricky and magical proof and and your first guidance think might be not to trust it
178
00:15:04.840 --> 00:15:07.640
but your next instinct would be to spend a
179
00:15:10.640 --> 00:15:13.080
Hundred hours thinking more about it and
180
00:15:13.760 --> 00:15:19.280
Trying to see how it all fits in with the barbacon and drum of putting it all together and it really happens to be a deep proof
181
00:15:19.280 --> 00:15:22.960
There are no flaws in this and it really does work even though it seems tricky
182
00:15:22.960 --> 00:15:26.640
I you say it doesn't work for a row or it doesn't work for a row or column
183
00:15:26.640 --> 00:15:30.480
But it does work for the diagonal because if I do this trick and I say oh it was number eight
184
00:15:30.480 --> 00:15:33.280
I just didn't show it to you. You can say well that's below me shy
185
00:15:33.280 --> 00:15:40.680
You can't be number eight because when I constructed this value I constructed the opposite in this row so it couldn't have been row number eight
186
00:15:41.840 --> 00:15:45.480
But if you just change this one I can tell you well it's number eight
187
00:15:45.480 --> 00:15:49.440
It's just the opposite of that. It's when you construct something down the diagonal that you know
188
00:15:49.440 --> 00:15:53.160
It's got to be different than all the rows that are already there because it hits all those rows
189
00:15:53.440 --> 00:15:58.840
You could you know you don't need it badly you could do like night night's moves would be okay probably
190
00:15:59.680 --> 00:16:03.720
You know and anything that it would be a little bit uglier to do the proof
191
00:16:03.720 --> 00:16:08.800
But anything that hits all the rows in unique places would probably be all right
192
00:16:08.800 --> 00:16:14.960
Yeah, John I'm a bit confused about the the finite and the
193
00:16:14.960 --> 00:16:17.040
I thought we started from the basis that
194
00:16:17.600 --> 00:16:25.240
However large the number of possible computer programs is finite. Oh, it's not finite. It's countable. Okay. It's countable
195
00:16:25.240 --> 00:16:29.880
That's different than finite. It's infinite, but it's the same infinite as natural numbers
196
00:16:30.400 --> 00:16:32.840
Okay, and this list is all possible
197
00:16:33.160 --> 00:16:36.400
Yes, right right and and if you want to say okay
198
00:16:36.400 --> 00:16:40.480
Well, I didn't have the sorry. I thought I had the list, but now that you mention it
199
00:16:40.480 --> 00:16:46.280
I should have put this one in there then I'll put that in there and we'll do the whole argument again and I'll come up with a new one
200
00:16:52.520 --> 00:16:54.280
You yes
201
00:16:54.280 --> 00:16:57.240
But typically what you do is you actually take your
202
00:16:57.680 --> 00:17:00.360
Characters that you make programs out of and you order them
203
00:17:00.360 --> 00:17:07.080
Let's go graphically in alphabetical order and anyone's that actually don't make legitimate programs you just define those programs to be the
204
00:17:07.400 --> 00:17:12.080
Programs that just do zeros all the way so you might get you know lots of rows that are zeros
205
00:17:12.080 --> 00:17:16.000
And that would be the junk you're talking about but that wouldn't affect this argument. It will still work
206
00:17:24.000 --> 00:17:28.440
Well because we're on the diagonal so it's programs working on themselves and
207
00:17:28.440 --> 00:17:40.600
The idea is that you can't figure out whether programs accept themselves or not and the part that falls apart is the part whether they're infinite loops because if it always terminated then we could fill out any of these
208
00:17:42.440 --> 00:17:47.640
Values and actually have it as a program so the only thing that really prevents us from doing it is that infinite loop idea
209
00:17:47.640 --> 00:17:55.080
I should say that what you do in theory of computation is you take this problem and then you reduce it to a gazillion other problems some of which are very far from this
210
00:17:55.080 --> 00:18:02.440
So one very important problem. This is an extremely important problem that is completely unable to be done is
211
00:18:03.120 --> 00:18:07.760
What if I give you it's a fancy word but it basically means a compiler?
212
00:18:07.760 --> 00:18:11.600
What if I give you two context free grammars if I give you two compilers?
213
00:18:11.600 --> 00:18:16.360
This is a compiler for scheme. This is a compiler B for scheme two people did it. They're competing
214
00:18:16.360 --> 00:18:19.160
They want to make a good compiler a better compiler and
215
00:18:19.160 --> 00:18:26.840
The question is I'm giving you these two compilers. I want you to just make sure before I test them against each other that they really do the same thing
216
00:18:27.400 --> 00:18:32.760
You know that they're both compilers for scheme that they both accept the same things and reject the same things
217
00:18:33.680 --> 00:18:39.800
That problem taking two context free grammars or two compilers and deciding whether they do the same thing is not
218
00:18:39.800 --> 00:18:50.560
Decidable in other words nobody could write a program to do that. That's a really important program to be able to write because I could use to compile the one program
219
00:18:51.440 --> 00:18:55.840
With the other program and then run the program through that make sure you get the same
220
00:18:56.440 --> 00:19:00.600
Well the check that you'd get the same input you'd have to run it on the infinite number of possible
221
00:19:00.600 --> 00:19:10.600
Inputs to check that they'd all be the same. That's the brute force way
222
00:19:14.600 --> 00:19:16.600
Then it would be the same
223
00:19:17.200 --> 00:19:22.520
No, I don't think it would necessarily be the same if you run one compiler on a bunch of scheme programs
224
00:19:22.520 --> 00:19:26.680
And you run another compiler and a bunch of scheme programs and there's an error in one of them
225
00:19:26.680 --> 00:19:33.680
It's not going to be the same if you run one compiler through another compiler then the first compiler if it has errors is
226
00:19:33.680 --> 00:19:38.440
Going to have errors when you run it through the the second compiler and the second pilot would work fine
227
00:19:39.160 --> 00:19:45.600
It's that that wouldn't help make any distinction between the equality here that one could still work fine and the other could still mess up
228
00:19:45.600 --> 00:19:47.600
Even if you're going to run one through the other
229
00:19:47.600 --> 00:19:56.600
So I mean it's true one can simulate the other but neither one can know whether those answers are all going to be the same.
230
00:20:00.600 --> 00:20:05.200
Yeah, after an infinite amount of time say the error is is say say there's no error
231
00:20:06.200 --> 00:20:11.400
How do you know they're always going to get the same answer you keep running and running and running and you have to keep trying
232
00:20:11.800 --> 00:20:14.040
Well, nobody knows any better way in any case
233
00:20:14.040 --> 00:20:19.600
So so there is no algorithm that's guaranteed to finish that tells you yes or no through all the cases yeah Rob
234
00:20:31.200 --> 00:20:36.640
Compiler behavior is is the term inistic but in order to check whether they're exactly equivalent
235
00:20:36.640 --> 00:20:42.440
We'd have to actually run the two compilers on every possible input
236
00:20:50.920 --> 00:20:52.920
That's true
237
00:20:52.920 --> 00:20:54.920
That's true
238
00:20:54.920 --> 00:21:11.920
There is no automatic way to check that you have that you have something that really works you can check for a particular compiler whether it worked but not for a general one
239
00:21:12.800 --> 00:21:19.560
There's no program that will take anything and tells you whether this really meets the specification that that another program is describing
240
00:21:19.560 --> 00:21:27.440
Okay, there are more specific ways of specifying what a program should do and you could check those but you can't just take two arbitrary
241
00:21:28.560 --> 00:21:33.200
Context for grammars and check whether they actually accept the same things or not that that's impossible
242
00:21:33.200 --> 00:21:35.600
But this is where we this is a
243
00:21:36.120 --> 00:21:40.160
Theory of computation discussion that we should have like in four months and not today solution
244
00:21:40.160 --> 00:21:43.080
But let's let's let's couple questions here Brian and then Sam
245
00:21:43.080 --> 00:21:48.440
I'm just imagining in case where the compiler is only different by say two lines of code that we can isolate
246
00:21:49.280 --> 00:21:54.880
It in particular cases you might be able to narrow down to a finite number of cases and and you're right
247
00:21:55.000 --> 00:22:00.520
But your program would have to work on any two compilers and the point is that it can't
248
00:22:01.240 --> 00:22:07.680
It might be able to if you could restrict your problem to a simpler subset of compilers it might be able to work
249
00:22:07.680 --> 00:22:15.320
But if it has to run on any two it fails so that's a good point. Yeah, Sam
250
00:22:28.320 --> 00:22:30.560
But it is countable I can show you how to count them
251
00:22:30.560 --> 00:22:40.600
Yeah, because programs are just are just the sequence of characters every program is built out of characters and every program has a finite length
252
00:22:41.600 --> 00:22:44.440
Therefore I can count all the programs in any language
253
00:22:44.440 --> 00:22:49.340
But you're right it is dependent on the fact that programs are countable programs are just syntactic structures
254
00:22:49.340 --> 00:22:51.340
What is in countable is what programs can do?
255
00:22:52.200 --> 00:22:59.040
The things programs can do is uncountable programs themselves are countable and that in nutshell is why there are things you want to do that
256
00:22:59.040 --> 00:23:01.040
There are no programs for
257
00:23:01.640 --> 00:23:03.440
Okay, I
258
00:23:03.440 --> 00:23:08.320
Wanted to something now that's a little less fun and you just need to see it because if I don't show it to you in class
259
00:23:08.320 --> 00:23:11.040
You'll say did you do that in class and I'll say well
260
00:23:11.040 --> 00:23:15.160
I didn't do it because it was boring. I wanted you to look it up. I'm gonna do it real quick
261
00:23:15.960 --> 00:23:19.720
I'm gonna do it real quick. It talks about functions. We talked about functions yesterday
262
00:23:19.720 --> 00:23:26.600
You need to know a few definitions about functions things that computer scientists and mathematicians take for granted and things that you probably
263
00:23:26.600 --> 00:23:30.160
May not know and and I don't want you to take it for granted
264
00:23:30.160 --> 00:23:34.960
So let me go through these definitions and explanations and it has to do with the idea of making a one-to-one car
265
00:23:34.960 --> 00:23:38.480
Spongebob showing that something's countable and what a one-to-one car
266
00:23:38.480 --> 00:23:42.080
Spongebob means because a function is not always a one-to-one car
267
00:23:42.080 --> 00:23:47.480
Spongebob so I want to talk about that for about ten minutes and then I'm gonna shift gears and we're gonna go back to sums
268
00:23:47.480 --> 00:23:49.480
I'm gonna show you how to evaluate sums
269
00:23:49.480 --> 00:23:56.320
When there's induction involved how to evaluate sums when there's no induction involved and we'll work our way towards recurrence equations
270
00:23:57.080 --> 00:23:59.080
all right, so functions
271
00:24:01.360 --> 00:24:03.360
functions and
272
00:24:03.880 --> 00:24:05.880
one-to-one car respondents
273
00:24:10.360 --> 00:24:14.680
Let's stick with one-to-one car respondents first because I hope you know what this means a one-to-one car
274
00:24:14.680 --> 00:24:22.080
Sponance is some sort of a correlation between a set of things here and a set of things here where every single thing here corresponds to a
275
00:24:22.320 --> 00:24:26.480
Particular thing here and vice versa. So here's a one-to-one car respondents
276
00:24:31.560 --> 00:24:33.560
We do this one yesterday
277
00:24:33.760 --> 00:24:36.760
The natural numbers to the positive even integers
278
00:24:37.400 --> 00:24:42.760
Okay, one goes to two two goes back to one two goes to four four goes back to two it's a one-to-one car Spongebob
279
00:24:42.760 --> 00:24:51.360
The function that represents this one-to-one car respondents is f of x equals to x anytime you have a one-to-one car
280
00:24:51.360 --> 00:24:52.960
respondents you have a
281
00:24:52.960 --> 00:24:57.600
Function that represents it now. What's a function? You're all supposed to know this but I'm just gonna review it
282
00:24:57.600 --> 00:25:02.720
The only thing that has to be true to make a function a function is that it's got to be a rule
283
00:25:02.720 --> 00:25:05.160
It's got to take something and transfer it to something else
284
00:25:05.160 --> 00:25:07.800
But the one thing that it can't do it can't change its mind
285
00:25:07.800 --> 00:25:14.000
Okay, if it takes one and decides that that goes to two then it can't take one and send it to three the next time
286
00:25:14.000 --> 00:25:19.760
You send in one so if it was a machine that has a little hole and you put the input in and then the output comes out another
287
00:25:19.760 --> 00:25:24.360
Hole every time you put a little ball that has one on it into that machine a two better come out
288
00:25:24.360 --> 00:25:29.620
If you put one on it the next day and a three comes out then that's not a function machine send it back to the company that makes
289
00:25:29.620 --> 00:25:38.600
Function machines and say you want it to fix it. Okay, it doesn't work functions can't change your mind. All right. Yeah question
290
00:25:47.600 --> 00:25:51.780
Sure sure because it still has a unique answer for every single input
291
00:25:52.040 --> 00:25:55.000
Right you could make it into lots of different cases if you wanted to
292
00:25:55.480 --> 00:25:57.000
Right sure
293
00:25:57.000 --> 00:26:05.040
All right, if you have a once-on-one correspondence then not only is this direction a function but the inverse direction is a function
294
00:26:06.160 --> 00:26:09.360
That's the forward direction. What's the function that goes backward?
295
00:26:11.520 --> 00:26:18.000
We'll call a g of x equals x divided by two and we sometimes write that
296
00:26:21.360 --> 00:26:24.920
We sometimes write this g of x is the inverse of f of x
297
00:26:24.920 --> 00:26:30.160
Okay, it's the it's the backwards. It's the thing that sends you back some terminology
298
00:26:32.240 --> 00:26:36.040
If you have a one-to-one correspondence then a function has an inverse
299
00:26:37.040 --> 00:26:43.200
There are functions that don't have inverses and there are functions that are not one-to-one correspondence
300
00:26:43.200 --> 00:26:48.200
And we need to talk about them and there's a couple definitions and I'll do some examples and then we'll let it go
301
00:26:49.280 --> 00:26:52.560
Okay, everybody okay so far so here's an example
302
00:26:52.560 --> 00:27:00.840
When you talk about functions you need to say where the inputs coming from and where the outputs going to that's called domain and
303
00:27:01.400 --> 00:27:02.920
And range
304
00:27:02.920 --> 00:27:04.920
month zero good
305
00:27:07.080 --> 00:27:16.160
Here's a function it takes acts it sends it to x squared the domain are the natural numbers the range is the natural numbers
306
00:27:16.160 --> 00:27:22.600
Okay, so this function takes only whole numbers greater than zero and it sends them to other whole numbers greater than zero
307
00:27:25.080 --> 00:27:27.080
Is this a one-to-one correspondence?
308
00:27:28.880 --> 00:27:30.880
It is right
309
00:27:34.880 --> 00:27:39.800
Is it a one-to-one correspondence yes or no yes? I say it is and trying to get you to say yes
310
00:27:40.440 --> 00:27:42.440
Now I'm saying no, what is it?
311
00:27:42.440 --> 00:27:45.720
Let's see what it means. Let's write it down
312
00:27:47.440 --> 00:27:49.440
One goes to one two goes to
313
00:27:51.680 --> 00:27:53.680
Four
314
00:27:56.080 --> 00:28:03.400
If I make this range go to natural numbers then there are some natural numbers on this side and if I put them in to my
315
00:28:03.400 --> 00:28:07.840
Inverse function or if I try to go backward what happens when I put three in here?
316
00:28:07.840 --> 00:28:09.840
I
317
00:28:10.240 --> 00:28:12.080
Don't get a natural number on the way back
318
00:28:13.600 --> 00:28:19.880
Right four goes back to two but three goes back to the square root of three and you know that there's no
319
00:28:20.480 --> 00:28:23.160
Whole number that's the square root of three so this
320
00:28:23.800 --> 00:28:30.240
function doesn't have an inverse per say going from n to n if I made this r to r real numbers to real numbers then
321
00:28:30.240 --> 00:28:42.640
Well, we'll do that well, but it's a different reason that's the issue does it have an inverse?
322
00:28:45.120 --> 00:28:48.560
A one-to-one correspondence and having an inverse or if and only if they're the same
323
00:28:53.920 --> 00:29:00.080
Right right right your choice of domain and range affects whether something has an inverse or not affects whether it's a one-to-one
324
00:29:00.080 --> 00:29:05.320
Correspondence you need to know what the domain is and the range is in order to answer this question. That's right Tony good
325
00:29:05.680 --> 00:29:09.240
All right, so let me do an example and explain a couple of definitions
326
00:29:09.240 --> 00:29:14.640
There are two definitions for functions that functions can be and if they're both of these then they have a one-to-one
327
00:29:14.640 --> 00:29:21.320
Correspondence and they have inverses the two things that make you have a one-to-one correspondents and an inverse is when a function is
328
00:29:21.320 --> 00:29:24.440
one-one and when a function is on two
329
00:29:24.440 --> 00:29:34.600
This does not mean the same as a one-to-one correspondents both of these together imply a one-to-one correspondence
330
00:29:34.600 --> 00:29:39.560
This is a separate idea and this is a separate idea. Let me explain what these are they're not hard ideas
331
00:29:39.560 --> 00:29:41.560
But you have to get the terminology a
332
00:29:42.600 --> 00:29:44.600
function is on to
333
00:29:46.360 --> 00:29:52.480
When every single value in the range has something that gets sent to it when there's nothing left out
334
00:29:52.480 --> 00:30:02.120
So is this function on to? No, it's not on to it's missing lots of values three doesn't have anything sent to it five doesn't have anything sent to it
335
00:30:03.360 --> 00:30:05.360
17 I
336
00:30:07.400 --> 00:30:11.800
Like to think about this in the following way. Here's a picture. Here's a domain
337
00:30:13.880 --> 00:30:15.880
That's that's on to that I just did
338
00:30:15.880 --> 00:30:25.320
Here's the range a function sometimes is written like this where we take something from the domain and we move it to something in the range
339
00:30:28.480 --> 00:30:34.920
Here's a function. Let me ask you a question about any function in the world is there ever more than one arrow coming out of this dot
340
00:30:35.760 --> 00:30:41.680
No, that's what a definition of a function means one arrow coming out of this dot in a function is
341
00:30:41.680 --> 00:30:48.080
Is it possible to have dots here that are empty? Yes, but what about an on to function?
342
00:30:48.600 --> 00:30:55.760
No, so an on to function means everything in the range has to have at least one arrow pointing to it and that's how I like to think of it at least
343
00:30:56.320 --> 00:30:58.320
one arrow
344
00:31:03.880 --> 00:31:05.880
To everything in the range
345
00:31:05.880 --> 00:31:16.960
At least one arrow to everything in the range you could have more than one arrow this guy could go here also
346
00:31:17.760 --> 00:31:19.760
It's possible
347
00:31:19.760 --> 00:31:20.760
a
348
00:31:20.760 --> 00:31:22.760
function is one one
349
00:31:25.160 --> 00:31:27.640
If you have it most one arrow coming in at
350
00:31:27.640 --> 00:31:34.480
At least one arrow to every dot means it's on to at most one arrow means it's one what I
351
00:31:37.280 --> 00:31:40.720
Think that's the easiest way to look at it. It's not the typical definition
352
00:31:41.680 --> 00:31:43.680
But it's virtually equivalent
353
00:31:44.920 --> 00:31:49.840
At least one arrow at most one arrow if you have at least one arrow and at most one arrow to everything in the range
354
00:31:49.840 --> 00:31:57.200
What does that mean that every dot in the range has exactly one arrow that means you can reverse the arrow orders and you get
355
00:31:58.840 --> 00:32:00.840
You get a function
356
00:32:00.840 --> 00:32:03.480
Right if you reverse these arrows do you get a function?
357
00:32:03.920 --> 00:32:09.680
No, because you got two things coming out of here if you reverse the arrows and you have an empty one then
358
00:32:11.000 --> 00:32:15.240
That's a problem because this is in the domain now and there's nothing in
359
00:32:16.360 --> 00:32:18.360
The range that it would get sent to
360
00:32:18.360 --> 00:32:20.360
So
361
00:32:20.360 --> 00:32:23.240
It's one to one even if two different
362
00:32:24.240 --> 00:32:27.120
Locations you can choose or not use the domain like the same here
363
00:32:27.480 --> 00:32:31.000
No, no one to one means there's a most one arrow
364
00:32:31.800 --> 00:32:37.200
Here's I'll give you an example of a function that's one one and not onto and a function that's onto and not one one
365
00:32:37.200 --> 00:32:40.480
Okay, okay, okay, so I'll give you examples of all these things in a second
366
00:32:43.720 --> 00:32:47.680
No, you can't because if it's not on to Chris you've got this empty
367
00:32:47.680 --> 00:32:50.600
Is this example with the square this example with the squares?
368
00:32:50.600 --> 00:32:53.040
It means you got lots of dots here that have no arrows pointing to them
369
00:32:53.600 --> 00:32:56.760
So when you go back from this domain to this range a
370
00:32:57.160 --> 00:33:03.520
function has to tell you what to do with everything that you throw in the in the input so when I throw this dot in
371
00:33:04.080 --> 00:33:07.360
It says sorry, I'm broke it and that's not a function
372
00:33:13.160 --> 00:33:16.920
No, there's a difference you know once one correspondence and a function being one one
373
00:33:16.920 --> 00:33:18.920
There are two different things
374
00:33:19.320 --> 00:33:24.760
Yeah, I know it's a bad choice of words, but that's what it is for a hundred years. So tough luck
375
00:33:25.600 --> 00:33:32.160
One one is different than a one-to-one correspondence a function is a one-to-one correspondence when it's both one one and on two
376
00:33:32.680 --> 00:33:34.200
Okay, yeah
377
00:33:41.200 --> 00:33:44.880
Fine Anthony suggested instead of calling this natural numbers
378
00:33:44.880 --> 00:33:51.120
We'll call this the squares of the natural numbers in which case this would be on to and one one in which case
379
00:33:51.120 --> 00:33:54.360
You would have a one-to-one correspondence and you'd have an inverse that's true
380
00:33:54.360 --> 00:33:59.880
And that's what Tony was getting at before that you could change domain and range and fix some of these problems
381
00:33:59.880 --> 00:34:06.920
But let me do a couple more examples so you'll get more of this so here is a function that as it's written now is on is not on to but is
382
00:34:08.040 --> 00:34:13.800
Is one one right there's no two things here that go to the same one on that side so it is
383
00:34:13.800 --> 00:34:17.400
One one but not on to one one
384
00:34:18.680 --> 00:34:20.680
Not on to
385
00:34:20.680 --> 00:34:22.680
Let me do another one
386
00:34:23.160 --> 00:34:31.400
Ceiling of x that means if it's a fraction it just raises it up to the nearest integer to the whole number and this goes from the real numbers to the natural numbers
387
00:34:32.720 --> 00:34:34.720
Or to the to the integers
388
00:34:35.840 --> 00:34:37.840
We'll include negative numbers
389
00:34:37.840 --> 00:34:49.320
Okay, so any real number you have in the whole world can go in here and we just push it up to the nearest integer that's bigger than it
390
00:34:50.960 --> 00:34:52.960
Is it on to
391
00:34:54.520 --> 00:34:57.720
Right because it gets every possible integer is it one one
392
00:34:59.440 --> 00:35:01.440
Couldn't possibly be there's a gazillion
393
00:35:02.480 --> 00:35:03.960
Real numbers
394
00:35:03.960 --> 00:35:09.360
1.2 1.4 1.7 1.8 that I'll go to two so this is on to
395
00:35:10.760 --> 00:35:12.760
But not
396
00:35:17.480 --> 00:35:19.480
How about this right?
397
00:35:19.480 --> 00:35:23.480
Right
398
00:35:29.840 --> 00:35:32.640
What about this function real numbers to real numbers I
399
00:35:33.240 --> 00:35:36.200
Take anything you give me I add one is it on to?
400
00:35:37.120 --> 00:35:42.800
Yes, is it one one? Yes, so this function should have an inverse. What would the inverse be?
401
00:35:42.800 --> 00:35:44.800
x
402
00:35:48.360 --> 00:35:56.140
Right as an inverse it's a one-to-one car respondents when Tara did that countable argument for pairs of numbers and she did that diagonal thing
403
00:35:56.140 --> 00:35:58.140
You know did she do that all right?
404
00:35:58.140 --> 00:36:03.280
So when she did that she came up with a function that function should have been a one-to-one car
405
00:36:03.280 --> 00:36:05.200
Spongebob and it should have an inverse
406
00:36:05.600 --> 00:36:09.200
You give me a number. I'll tell you where it is in the chart. You tell me where you are in the chart
407
00:36:09.200 --> 00:36:11.200
I'll tell you what number that connects to
408
00:36:11.200 --> 00:36:13.200
Okay
409
00:36:13.600 --> 00:36:15.600
Questions about this
410
00:36:15.600 --> 00:36:17.600
Yes, Sharon
411
00:36:23.360 --> 00:36:25.360
Yes has at least one error right
412
00:36:25.360 --> 00:36:31.800
How do we where do we have to the fact that if we inverse everything in the domain needs to have been mapped from?
413
00:36:32.680 --> 00:36:34.680
Is that colored by one one
414
00:36:39.920 --> 00:36:44.000
Yeah, because if we reverse and the our domain then becomes arranged
415
00:36:44.000 --> 00:36:56.960
Where we have to reverse everything that our form and domain has to get now to?
416
00:36:56.960 --> 00:37:04.320
Because there's always for any function an arrow coming out of every dot in the domain. Okay, so we can't have more things. You can't have empty things in the domain
417
00:37:04.320 --> 00:37:10.240
That are left open that's part of the definition of a function. Not only can't you change your mind, but you can't say I
418
00:37:10.240 --> 00:37:15.840
Don't know what to do with this input if you give me the domain that means you're willing to for me to put anything in it
419
00:37:16.240 --> 00:37:20.680
Okay, that's like a candy machine saying insert nickels and quarters and nickels are fine
420
00:37:20.680 --> 00:37:24.160
And then when you insert the quarter and you press your Hershey's bar. It says sorry
421
00:37:24.800 --> 00:37:31.400
You know can't take quarters at this time, right? So yeah, right, but that's but that's a bad function
422
00:37:31.400 --> 00:37:39.600
Right that's uh, yeah, well, that's a busted machine. Here one more example real fast. Here's a function
423
00:37:43.320 --> 00:37:46.880
Have finite function one goes to one two goes to one three goes to three
424
00:37:48.880 --> 00:37:50.880
Is it on to?
425
00:37:50.880 --> 00:37:55.280
No, is it one one nope does it have an inverse? No?
426
00:37:55.280 --> 00:38:01.240
Yeah, yeah, here's here right here's how you write finite functions
427
00:38:02.120 --> 00:38:06.600
The domain is the set one two three the range is the set
428
00:38:07.360 --> 00:38:09.360
one two three
429
00:38:09.360 --> 00:38:16.520
Here's the function f f of one equals one and two equals two f of three equals three
430
00:38:17.120 --> 00:38:19.120
Oh, yeah
431
00:38:19.120 --> 00:38:21.200
Thanks. Yes, so you could write it. I just can't right?
432
00:38:21.200 --> 00:38:27.800
Right a finite function you can write by just specifying the things we're used to writing functions as formulas
433
00:38:27.800 --> 00:38:33.880
And you think of a function as a formula, but a function is not a formula function is any kind of correspondence between the domain and a range
434
00:38:33.880 --> 00:38:37.480
And if it's a finite set then you can always describe it by just listing it
435
00:38:45.960 --> 00:38:49.120
If your range is integers then two is supposed to go someplace
436
00:38:49.120 --> 00:38:56.100
I don't understand all the hours point of two of all the hours pointed to that's okay
437
00:38:58.360 --> 00:39:01.280
We can do that that's not a function
438
00:39:03.280 --> 00:39:09.440
All right, so then you can write f of x equals two. Yes instead of writing f of one equals two f of two equals two of three equals two
439
00:39:10.720 --> 00:39:13.560
It's also not one one. It's also not on two right
440
00:39:13.560 --> 00:39:18.040
Yeah, I'm not a recent just look like I'm gonna do it
441
00:39:20.040 --> 00:39:22.040
That wasn't what you were thinking
442
00:39:28.480 --> 00:39:30.480
Yes
443
00:39:31.280 --> 00:39:35.520
It's like it's like you got to decide if you're punting or not on fourth down before
444
00:39:36.840 --> 00:39:41.640
Well in a kids game before I set the defense you got to decide what your range is and
445
00:39:41.640 --> 00:39:46.480
And specify that and then tell me what the function is you can't just say oh my ranges whatever
446
00:39:46.480 --> 00:39:50.680
I'm gonna hit two and if you do then tell me a range is that not exclude one and three from the range
447
00:39:51.440 --> 00:39:53.440
Okay
448
00:39:55.040 --> 00:39:59.960
They call the code domain they pop the set of all possible values and the range
449
00:40:00.480 --> 00:40:04.320
Be set of values that are actually hit by the function. That's what Sam decided
450
00:40:07.200 --> 00:40:09.200
That's it you just said right?
451
00:40:09.200 --> 00:40:12.480
Was actually hit oh no, no the range is a thing that's well
452
00:40:15.920 --> 00:40:18.800
Yeah, but you'll notice I did not use the word code domain
453
00:40:25.640 --> 00:40:27.640
This is not a pike
454
00:40:29.360 --> 00:40:31.360
Right here's
455
00:40:32.600 --> 00:40:34.600
Oh geez
456
00:40:34.600 --> 00:40:39.240
Anyway, I like to give you as few terms as you need to actually understand the idea and
457
00:40:40.320 --> 00:40:42.320
sometimes that's zero
458
00:40:43.920 --> 00:40:45.920
Sometimes
459
00:40:47.480 --> 00:40:54.600
Okay, a couple quick things now for a little bit of review in orders of growth with functions. Oh, we got a lot more
460
00:40:54.600 --> 00:41:07.960
We're gonna do two examples just because there's one problem on the problem set that I think is really crucial for
461
00:41:08.520 --> 00:41:10.920
Experimenting with and for learning about orders of growth
462
00:41:10.920 --> 00:41:17.320
It's the problem where I gave you a gazillion functions and I asked you to order that I said if they're big theta of each other
463
00:41:17.320 --> 00:41:20.920
Put them on the same level, but if one is actually you know
464
00:41:20.920 --> 00:41:24.720
Larger than the other say small O of the other then
465
00:41:25.480 --> 00:41:27.280
Then actually put them in order
466
00:41:27.280 --> 00:41:31.400
It's a really really useful problem because you have a lot of pairs of functions to compare and it will
467
00:41:32.120 --> 00:41:36.520
force you to develop intuition that you wouldn't normally get by just doing the everyday typical
468
00:41:36.920 --> 00:41:41.560
Examples so here's a simple example of the kind of thing that might come up on that problem
469
00:41:41.560 --> 00:41:46.360
Then I'll do a harder one the question is how do these compare to one another and the answer is
470
00:41:46.360 --> 00:41:52.720
That they're the same and they're both x log x. They're both big theta x log x. Let me show you why
471
00:41:53.640 --> 00:41:57.760
You all should know this but I'll show you why anyway log of x to the x equals
472
00:41:58.760 --> 00:42:00.160
x log x
473
00:42:00.160 --> 00:42:05.400
So it's certainly big theta x log x because the constant is just one for both cases
474
00:42:06.040 --> 00:42:11.240
It's less than or equal to x log x where the constants one. It's greater than or equal to x log x where the constants one
475
00:42:11.680 --> 00:42:14.000
That's one of those log rules you learned in month one
476
00:42:14.000 --> 00:42:16.000
But about this one this one is
477
00:42:17.160 --> 00:42:18.680
x times
478
00:42:18.680 --> 00:42:22.040
two log x which equals two x log x
479
00:42:23.400 --> 00:42:25.400
So that's going to be
480
00:42:25.400 --> 00:42:33.440
Big O of x log x because it's less than or equal to two x log x and it's going to be greater than or equal to x log x for a constant of one
481
00:42:33.960 --> 00:42:35.960
So you can a big R and big omega
482
00:42:35.960 --> 00:42:40.120
So this is also big theta x log x intuitively the constant doesn't matter
483
00:42:40.120 --> 00:42:45.520
So x log x and two log x are the same these two functions are the same and you put them on the same lot
484
00:42:46.680 --> 00:42:48.680
Right, let me do a more complicated example
485
00:42:49.440 --> 00:42:54.840
You're probably thinking oh gee. I wish I really had absorbed all those log rules and you would be right
486
00:42:57.760 --> 00:43:04.680
The more those are automatic the faster you're going to be able to have a good guess as to which function is and when they're not automatic
487
00:43:04.680 --> 00:43:09.640
It's going to seem like you're working hard, but the harder you work the more automatic little be the next time so
488
00:43:10.360 --> 00:43:12.360
Here's a hard one
489
00:43:14.320 --> 00:43:16.320
We're a harder one at least
490
00:43:18.960 --> 00:43:22.440
X to the log x log x to the x I just reversed them
491
00:43:24.840 --> 00:43:29.320
Two different ones yeah, we're going to compare them which ones bigger than the other are they the same?
492
00:43:29.320 --> 00:43:31.760
What are they compared to so at this point?
493
00:43:31.760 --> 00:43:37.360
You know when you're a beginner you just look at oh geez. I never saw anything like this do we ever do anything like this?
494
00:43:37.920 --> 00:43:41.160
It's not fair to put this on the exam if we didn't do anything like this in class
495
00:43:43.880 --> 00:43:44.880
Uh-oh
496
00:43:47.120 --> 00:43:49.120
Look at this example
497
00:43:49.240 --> 00:43:53.760
You need to be able to compare these two things they don't look very easy to compare if you have some intuition
498
00:43:53.760 --> 00:43:56.760
Mathematically you probably already have a good guess as to which one is harder
499
00:43:56.760 --> 00:44:01.680
But if your intuition is still at a at a beginner's level or even an intermediate level you might not know where to go
500
00:44:01.680 --> 00:44:07.160
So let's try to at least get this into a better form. Let me give you a goal if it looked like this
501
00:44:11.080 --> 00:44:13.080
Would you have a guess which one is bigger?
502
00:44:15.920 --> 00:44:21.760
This one looks bigger because this exponent is bigger than that and and these are just a factor whether they actually are
503
00:44:21.760 --> 00:44:27.080
You know one's bigger than the other maybe they're big theta you'd have to work through the definition. I should mention
504
00:44:27.480 --> 00:44:34.920
As a good thing to remember that when you have exponents are the same if this is bigger than this one normally as a function
505
00:44:34.920 --> 00:44:40.800
It's big oh it's it's a larger specifically than this then this whole thing is larger than this as well
506
00:44:41.000 --> 00:44:45.560
And that's something you could prove and in some of the exercises you end up discovering this yourself
507
00:44:46.480 --> 00:44:49.480
But but it doesn't look like that we have to make it look like that
508
00:44:49.480 --> 00:44:52.360
We have to make it so that we have some chance of doing this
509
00:44:57.120 --> 00:44:59.120
Take logs on both sides
510
00:45:00.720 --> 00:45:02.960
What base any base you want?
511
00:45:06.960 --> 00:45:09.840
Okay, what Sam is suggesting is more or less what I want to do
512
00:45:09.840 --> 00:45:13.040
But I like to present it in a mildly different way. So here's what I'm going to say
513
00:45:13.040 --> 00:45:14.200
I
514
00:45:14.200 --> 00:45:20.320
Want to introduce this in a slightly different way because it relates to something you'll see in recurrence equations the idea of changing the variables
515
00:45:20.760 --> 00:45:26.560
Changing the variables and making it look a little more like what you like and it's essentially equivalent to taking the logs of both sides
516
00:45:29.040 --> 00:45:36.760
Why am I going to make this substitution of this change of variable because I'd like it to be two to the something versus two to the something like I showed you before
517
00:45:36.760 --> 00:45:42.720
So let's go ahead and do this and see how things simplify and if you think how would I know to do it well?
518
00:45:44.120 --> 00:45:47.520
You guess you try some tricks you get better at seeing which trick works
519
00:45:49.240 --> 00:45:51.960
It's not very satisfying, but that's the best I can do right now
520
00:45:54.640 --> 00:46:00.520
Let's try to calculate x and log x so we can substitute in there and change everything to y change the variable
521
00:46:00.520 --> 00:46:07.600
x is two to the y we chose that as our substitution. What is log of x going to be take base two? Why?
522
00:46:08.320 --> 00:46:12.640
Now things now the logs are gone. You know logs make you sick. So get rid of them
523
00:46:12.800 --> 00:46:18.120
So x to the log x. What does that look like two to the y to the
524
00:46:19.240 --> 00:46:21.600
To the y and comparing it to what's this?
525
00:46:22.840 --> 00:46:24.840
Why to the
526
00:46:24.840 --> 00:46:33.840
It's still doesn't look quite what we want, but if I giving you this to begin with you probably wouldn't have had a complete horrible not in your stomach just a mild one
527
00:46:34.480 --> 00:46:39.840
Look at these two. They're different from the two we started with, but they are still relatively
528
00:46:40.800 --> 00:46:42.800
comparable. I just changed the variable
529
00:46:44.120 --> 00:46:46.120
How can I compare these two now?
530
00:46:46.120 --> 00:46:54.600
You have two y to the y squared. Let's look at this one two to the y to the y is the same as two to the y squared
531
00:46:55.440 --> 00:46:58.160
Okay, two to the a to the b is two to the a times b
532
00:46:59.360 --> 00:47:02.680
How can we write this in terms of two to the something is there any way?
533
00:47:04.680 --> 00:47:06.240
This y
534
00:47:06.240 --> 00:47:10.480
Let's say I wanted to take y and write it as two to the something it would be two to the y
535
00:47:10.480 --> 00:47:12.480
two to the log y
536
00:47:14.760 --> 00:47:20.960
Again with the logs two to the log y is y that's the definition of log y two to the log of y is
537
00:47:21.880 --> 00:47:26.240
Equal to y so I substitute that for y and I still have the two to the y up here
538
00:47:27.360 --> 00:47:30.800
So what's this equal to oh this is not equal. This is a question more
539
00:47:31.760 --> 00:47:35.760
Two to the log y to the two to the y. Let's finish it up. It's two to the
540
00:47:35.760 --> 00:47:44.840
log y times two to the y so now I've got what I promise we got two to the something equal two to the something and let's compare
541
00:47:44.840 --> 00:47:49.640
y squared to log base two y to the two to the y I didn't quite get that last step
542
00:47:50.480 --> 00:47:52.480
To the a
543
00:47:53.000 --> 00:47:58.120
That's a good point two to the two to the a to the b is two to the a times b
544
00:47:58.640 --> 00:48:02.480
Okay, it's the same step we actually used here two to the y to the y is two to the y squared
545
00:48:02.480 --> 00:48:06.460
How did you get the two to the two to the log y equals y?
546
00:48:09.160 --> 00:48:11.360
That's the definition of what log y means
547
00:48:12.480 --> 00:48:20.020
This is exactly the definition. There's no there's no idea there except the definition log y is the number that if you raise two to that number you get y
548
00:48:20.520 --> 00:48:22.480
And that's I just put it in there
549
00:48:22.480 --> 00:48:28.080
So the rule of thumb is you can always get rid of a y and turn it into two to anything you want so we did that we
550
00:48:28.080 --> 00:48:34.820
Forced it I twisted the arms of these formulas until they looked the way I wanted them to look and I hope to God when I was all done
551
00:48:34.820 --> 00:48:37.360
That the exponents would be something that were more obviously
552
00:48:38.040 --> 00:48:40.040
comparable than what I started with
553
00:48:40.600 --> 00:48:44.280
So let's look at the exponents now here. I have y squared here. I have
554
00:48:44.840 --> 00:48:48.360
Two to the y times log base two of y which ones bigger?
555
00:48:52.560 --> 00:48:54.560
Don't take too long
556
00:48:54.560 --> 00:49:01.480
You did this which one's bigger two to the y or y squared two to the y kills y squared. It's a mismatch
557
00:49:03.240 --> 00:49:09.160
No, no, it's log base two y times two to the y now this is just like this is like just bonus
558
00:49:09.600 --> 00:49:13.280
This is like take this huge guy, you know and in you know
559
00:49:13.280 --> 00:49:17.600
I don't know the Goldberg guy that wrestling guy right you think a huge guy that's two to the y
560
00:49:18.360 --> 00:49:21.680
Put him up against me in the wrestling rink y squared
561
00:49:21.680 --> 00:49:27.000
Just some typical average guy and then give Goldberg like somebody to tag in an extra log y as if it wasn't enough
562
00:49:27.000 --> 00:49:30.640
Just have two to the y this just kills this it's it's there's no match
563
00:49:32.480 --> 00:49:35.000
Right right boom right right head into the turnbuckle
564
00:49:37.160 --> 00:49:41.800
All right, what's the point therefore this one is bigger and at this one's bigger that means
565
00:49:42.840 --> 00:49:44.840
This one's bigger
566
00:49:44.840 --> 00:49:51.840
Two to the y squared versus two to the log y times two to the y
567
00:49:54.760 --> 00:49:56.760
Compare this to this
568
00:49:56.760 --> 00:50:07.760
It's times right that's what Chris was saying before
569
00:50:17.200 --> 00:50:22.600
Well, we haven't said that at all all we said is that this one is definitely going to be bigger than this one
570
00:50:22.600 --> 00:50:28.120
But if you wanted to put it back into big on notation we could say that this is you know order
571
00:50:28.560 --> 00:50:32.760
Every function is order itself. This is order two to the two to the y times log y
572
00:50:32.760 --> 00:50:37.480
But if you wanted to put it back you'd have to redo this and we just end up getting this so
573
00:50:39.480 --> 00:50:43.840
The idea of what it really is is kind of like it's not really a well-defined question
574
00:50:43.840 --> 00:50:46.640
It's not like every function is big. Oh something unique
575
00:50:46.800 --> 00:50:50.280
They're big. Oh, all the other functions that are that are that are larger than that
576
00:50:50.280 --> 00:50:56.400
So so you don't look for some canonical one to compare it to you just compare it to another one
577
00:50:57.520 --> 00:51:05.280
Typically we like to put all functions into one of typical you know like n or n log n or n squared or two to the n
578
00:51:05.440 --> 00:51:09.960
I mean these are the ones that come up so often so we tend to like to take any weird thing that comes up and
579
00:51:10.320 --> 00:51:16.160
Figure out where it sits relative to these but that's just because these come up a lot. There's nothing really special about that
580
00:51:16.160 --> 00:51:24.000
I want to talk about sums I want to talk about this on in particular and I want to connect it back to your problem sets
581
00:51:24.080 --> 00:51:33.760
We're going to talk about sums. We're going to work our way to recursion back to sums and then say go buy to sums and logic and all this stuff and move on to a different topic as of tomorrow
582
00:51:35.920 --> 00:51:37.920
Recurrence equations and recursion
583
00:51:39.760 --> 00:51:41.760
Today's going to overlap right now in this
584
00:51:41.760 --> 00:51:48.280
You've done a bunch of proofs by induction some of you definitely get the idea some of your kind on your way and some of you are like
585
00:51:48.840 --> 00:51:51.800
Like hate the idea and and don't get it yet at all and
586
00:51:52.640 --> 00:51:56.240
And you'll all will get it but it'll take some time some problems
587
00:51:56.240 --> 00:52:01.160
I say are screaming for induction and some problems. I say are not so natural and if you get that idea
588
00:52:01.160 --> 00:52:03.520
You probably know what I'm talking about and if you don't get that idea
589
00:52:03.520 --> 00:52:06.480
It just seems like what's he talking about screaming for induction?
590
00:52:06.480 --> 00:52:10.240
So I want to give you an example in one of the problems that I show you a
591
00:52:10.240 --> 00:52:12.240
particular
592
00:52:13.400 --> 00:52:15.400
Theorem about cubes
593
00:52:25.720 --> 00:52:28.960
That's the theorem right this is a theorem again from that same
594
00:52:29.920 --> 00:52:31.920
medieval math book back in the
595
00:52:32.120 --> 00:52:33.480
1321
596
00:52:33.480 --> 00:52:41.960
Lavy Ben Gershone proved this theorem and he proves it by induction and if you look in your problem set what he discovers before he proves this theorem is
597
00:52:43.360 --> 00:52:47.240
Another theorem which just lends itself to discovering this
598
00:52:48.880 --> 00:52:52.000
Does anybody remember what that other theorem is anybody do this yet?
599
00:52:52.000 --> 00:53:09.400
What's the theorem he he proved? Well, I believe you know what it is but now the question is can we can we state it?
600
00:53:15.040 --> 00:53:18.320
He proves something like this what does he say this is equal to?
601
00:53:18.800 --> 00:53:20.080
Does he do this?
602
00:53:20.080 --> 00:53:22.320
No, this is not what you mean right no
603
00:53:29.320 --> 00:53:31.320
Excellent
604
00:53:32.080 --> 00:53:37.560
And that's I think that's what you're trying to say Chris you go up to n minus one you square it right
605
00:53:39.160 --> 00:53:40.680
plus
606
00:53:40.680 --> 00:53:42.680
And cube the one is that equal
607
00:53:42.680 --> 00:53:52.920
Something like that right is that right and he proves this with algebra he proves it's not so hard to come up with this
608
00:53:53.160 --> 00:53:57.160
Let's make sure it's right before he says that's so hard to come up with it. I think that's right
609
00:53:58.640 --> 00:53:59.560
Good
610
00:53:59.560 --> 00:54:05.520
It's definitely right he proves this he comes up with this analogy we discover it one day when you discover something like this
611
00:54:06.200 --> 00:54:10.440
All you got to do is look at it for about three more seconds to say oh
612
00:54:10.440 --> 00:54:17.040
If this equals n cube plus this I'll just do it again. What is this equal?
613
00:54:21.720 --> 00:54:24.280
And minus one cubed plus
614
00:54:32.160 --> 00:54:36.240
Just do it again and you can do it again and again and what happens?
615
00:54:36.240 --> 00:54:44.320
This stays on the right side and this keeps disappearing turning into cubes one down as you go until sooner or later
616
00:54:44.560 --> 00:54:50.640
You get to the base case the thing that stops you and you get one here at the end and that's where this comes from
617
00:54:51.640 --> 00:54:56.600
This theorem is a screaming induction theorem from the discovery of this theorem
618
00:54:57.760 --> 00:55:04.080
It's just natural. It's recursion. It's all the stuff you did last month you want to figure out you want to solve this for n?
619
00:55:04.080 --> 00:55:07.520
Do it for n minus one and add n cubed
620
00:55:08.200 --> 00:55:13.800
What happens then recursively you do it for n minus one yet n minus one cubed you call the recursion again
621
00:55:13.800 --> 00:55:15.480
It's exactly recursion
622
00:55:15.480 --> 00:55:21.360
So he discovers a recursive theorem or a relationship like this and that implies a bigger theorem a more interesting theorem
623
00:55:22.160 --> 00:55:27.200
Anything like that is a theorem that's screaming for induction and anything like this is this theorem
624
00:55:27.200 --> 00:55:28.840
That's kind of screaming not to do induction
625
00:55:28.840 --> 00:55:34.400
There isn't any natural theorem like this that looks just as clean for this example
626
00:55:34.600 --> 00:55:38.280
So if you actually look into Lavey's book and see what he does he has a long
627
00:55:38.600 --> 00:55:43.880
Sequence of other completely complicated algebra ideas to come up with this formula even though you can bet
628
00:55:43.880 --> 00:55:46.520
He understood that he could have done this by induction
629
00:55:46.520 --> 00:55:49.680
He just thought it was a terrible way to do it because it was badly motivated
630
00:55:50.360 --> 00:55:54.200
Here he did it by induction because this is the way he was motivated to solve the problem
631
00:55:54.200 --> 00:55:58.040
Here he didn't do it by induction because he didn't think that this was a nice way to do it
632
00:55:58.040 --> 00:56:00.920
So we're going to do this today. I can tell you what the formula is here
633
00:56:04.880 --> 00:56:06.880
It's equal to this
634
00:56:07.400 --> 00:56:11.600
We're going to calculate this formula not by induction although we could do it by induction
635
00:56:11.600 --> 00:56:15.160
It's just some algebra in fact if you want to practice it
636
00:56:15.160 --> 00:56:19.440
It's another good example to practice induction on we're going to do it by a completely different method
637
00:56:19.440 --> 00:56:23.960
This method will not only show us what I mean by a different kind of a proof
638
00:56:23.960 --> 00:56:31.040
But it will help you learn a really important thing how to manipulate sums manipulating sums is a crucial thing to be able to do in
639
00:56:31.040 --> 00:56:37.120
The analysis of algorithms and in manipulating sums at some point the dot dot dot notation isn't quite good enough
640
00:56:37.120 --> 00:56:41.920
Or quite helpful enough so we end up inventing something called a sigma notation and in this proof
641
00:56:41.920 --> 00:56:47.160
You're really going to have a need for it. It's just too hard to do this without the sigma notation and up till now
642
00:56:47.160 --> 00:56:51.280
I haven't introduced it because I think it just makes people have a language barrier to the idea
643
00:56:51.280 --> 00:56:54.640
But in this proof we're going to need it because the language is really necessary
644
00:56:54.640 --> 00:56:59.200
I'm going to avoid it until we absolutely need it and then I'll introduce the notation
645
00:56:59.480 --> 00:57:02.440
Here's how we start to do this problem. I'm going to motivate it a little bit
646
00:57:02.440 --> 00:57:05.800
The first thing we start to do is we notice this particular series
647
00:57:05.800 --> 00:57:21.920
If you add up the odd integers up to some point you get square numbers
648
00:57:21.920 --> 00:57:28.520
People knew this documented you know back 300 CE the late group period people knew this
649
00:57:28.520 --> 00:57:32.760
It's not so hard to discover this you can discover geometrically here's one
650
00:57:32.760 --> 00:57:39.200
Here's one plus three here's one plus three plus five
651
00:57:44.640 --> 00:57:50.280
Everybody see what's going on every time you add the next odd number you just wrap around the next shell the square
652
00:57:51.360 --> 00:57:57.000
Yeah, it's kind of a proof you could prove this by induction this does scream for induction
653
00:57:57.000 --> 00:58:05.560
Let's say that all the sum of these add up to n squared what happens when you add one more?
654
00:58:05.560 --> 00:58:13.240
n squared you add one more what do you add yet two n plus one that's the next odd number and what is that equal?
655
00:58:13.240 --> 00:58:23.040
n plus one squared that was such a fast proof by induction that I left out all the gazillion steps that you would really need to put in to make it completely clear
656
00:58:23.040 --> 00:58:27.400
But the just of this proof if you would go ahead and write it clearly which I'm not going to do right now
657
00:58:27.400 --> 00:58:29.960
Maybe I'll come back and do it later you probably could use the review
658
00:58:29.960 --> 00:58:34.640
But the just of this proof is adding on the next number to a square gets you the next square
659
00:58:34.640 --> 00:58:39.280
And if you could write that out clearly step by step with the base case, etc
660
00:58:39.280 --> 00:58:42.600
You'd have a proof by induction of this but let's just assume this is true now
661
00:58:42.600 --> 00:58:45.320
We all know it's true. We're going to use this to get this formula
662
00:58:46.320 --> 00:58:48.320
So let me stop for a second
663
00:58:48.320 --> 00:58:55.200
Question so far all we have with these odd numbers adding up to squares we're going to come up with this in a couple of minutes
664
00:58:55.200 --> 00:59:16.200
Everybody okay, here we go
665
00:59:25.200 --> 00:59:38.200
Here's my list of squares one plus four plus nine plus sixteen plus what does this one turn out to be?
666
00:59:38.200 --> 00:59:40.200
n squared
667
00:59:40.200 --> 00:59:51.000
Let's check to make sure that's true if n is three the last term is five and I get three squared
668
00:59:51.000 --> 00:59:58.200
So the last term is two n minus one here if I add up these numbers I get the sum of the squares
669
00:59:58.200 --> 01:00:03.040
What layvy did is to add up these numbers by adding up these numbers
670
01:00:03.040 --> 01:00:08.840
But add them up a column at a time here the squares just add them up but change the rows in the columns
671
01:00:08.840 --> 01:00:12.120
Does everybody with me so far stop if you're not
672
01:00:12.120 --> 01:00:14.120
Questions
673
01:00:14.120 --> 01:00:22.720
Is it two n minus one? Yes, because you have like what's in the case of one three five seven
674
01:00:22.720 --> 01:00:30.520
In the case of one three five seven the n is going to be four and that's equal to sixteen four squared is sixteen
675
01:00:30.520 --> 01:00:32.520
Okay
676
01:00:35.520 --> 01:00:37.520
Let's add these up
677
01:00:37.520 --> 01:00:46.360
Let's add these up here is where not having good notation
678
01:00:46.360 --> 01:00:51.280
Gets a beginner to the point where they give up and having good notation
679
01:00:51.280 --> 01:00:56.280
Smooth the mathematician right by how many ones do we have here?
680
01:00:56.280 --> 01:00:59.760
Everyone agree?
681
01:00:59.760 --> 01:01:03.320
One two three four five all the way up to n
682
01:01:03.320 --> 01:01:10.320
So true n times one how many three do we have?
683
01:01:10.320 --> 01:01:17.720
N minus one times three how many five n minus two times five
684
01:01:17.720 --> 01:01:24.320
And minus three times seven all the way down to the last case where it is
685
01:01:24.320 --> 01:01:31.800
Two n minus one times one how are we going to add this mess up
686
01:01:31.800 --> 01:01:36.320
So here's where we need a better notation to help us add this up
687
01:01:36.320 --> 01:01:40.800
You might be able to avoid it but I don't see an easy way to avoid it
688
01:01:40.800 --> 01:01:48.320
What I want to do here is notice how the first term here is changing and how the second one is changing
689
01:01:48.320 --> 01:01:54.520
Here's the notation that we're going to use
690
01:01:54.520 --> 01:02:00.360
This means the sum of we're going to start with
691
01:02:00.360 --> 01:02:07.360
One two and figure out the first term and the second term
692
01:02:07.360 --> 01:02:12.360
One n is one what's the first term?
693
01:02:12.360 --> 01:02:17.360
It's n second term n minus two et cetera
694
01:02:17.360 --> 01:02:26.360
What about the second terms here? This is one three five et cetera
695
01:02:26.360 --> 01:02:33.360
What's this one going to be?
696
01:02:33.360 --> 01:02:36.360
What's this one going to be?
697
01:02:36.360 --> 01:02:40.360
Let's see what this is. When I'm at the first term it's n
698
01:02:40.360 --> 01:02:43.360
It's always n minus the number that's one smaller than this
699
01:02:43.360 --> 01:02:49.360
So it's n minus i plus one
700
01:02:49.360 --> 01:02:55.360
If I'm on the fourth one this would be n minus four plus one that's n minus three
701
01:02:55.360 --> 01:03:02.360
Here's the general term of the first one. What's the general term for this one?
702
01:03:02.360 --> 01:03:05.360
When you're at one you're at one, when you're at two you're at three
703
01:03:05.360 --> 01:03:14.360
So double it and subtract one
704
01:03:14.360 --> 01:03:23.360
What I'm really doing here is multiplying those pairs as i starts at one and goes all the way down to what's the last one that i goes to
705
01:03:23.360 --> 01:03:29.360
Starts at one and goes down to or goes up to and so here's how we write it
706
01:03:29.360 --> 01:03:39.360
i starts at one goes up to n and we're going to add up all these terms n minus i plus one times two i minus one
707
01:03:39.360 --> 01:03:44.360
Now I could have done this using the dot notation but it would have been a little bit uglier
708
01:03:44.360 --> 01:03:50.360
This really summarizes what I just said. We have these two pairs of things that are multiplied by each other
709
01:03:50.360 --> 01:03:59.360
They change their values as i changes from one to n. When i is one they should be n and one
710
01:03:59.360 --> 01:04:06.360
When i is two they should be n minus one times three. So if I just want to add these up I'm adding up this sum
711
01:04:06.360 --> 01:04:09.360
And you're thinking well what's the point of writing this like this? How does it help?
712
01:04:09.360 --> 01:04:13.360
It helps a lot if you can think about what's going on and unravel this
713
01:04:13.360 --> 01:04:17.360
So we're up to here and we're about to finish up
714
01:04:17.360 --> 01:04:24.360
And it gets a little bit hairy but here's where you have to learn how to manipulate sums. If you can learn to manipulate these things you'll be doing great
715
01:04:24.360 --> 01:04:29.360
Okay, other questions so far before I finish with this. Questions, questions.
716
01:04:29.360 --> 01:04:34.360
Good. Let me make some room here so we can actually manipulate this
717
01:04:34.360 --> 01:04:44.360
And I'll keep our goal up here so we can keep track of where we're headed
718
01:04:44.360 --> 01:04:51.360
Here's what we're going to do with this sum. We're going to do what you always try to do
719
01:04:51.360 --> 01:04:55.360
Even without any particular good intuition. We're going to multiply these things out together.
720
01:04:55.360 --> 01:05:00.360
If we multiply them out together then we have the sum of the first plus the sum of the second plus the sum of the third.
721
01:05:00.360 --> 01:05:06.360
We can split it up into separate sums each of which might be easier than the sum of this product.
722
01:05:06.360 --> 01:05:14.360
So let's multiply it out and see if we can split it up into smaller pieces.
723
01:05:14.360 --> 01:05:22.360
What do I get? Let's do it. 2i n
724
01:05:22.360 --> 01:05:35.360
Minus 2i squared plus 2i minus n plus i
725
01:05:35.360 --> 01:05:42.360
Minus 1. Let's see if we can fiddle with these things a little bit.
726
01:05:42.360 --> 01:05:50.360
Make them simpler if possible and then do the sum of the ones we need to.
727
01:05:50.360 --> 01:06:01.360
Are we right it up here? Okay. Ej. Simple by this a little for me. What goes together?
728
01:06:01.360 --> 01:06:08.360
You can get rid of the plus 2i plus i and make it plus 3i.
729
01:06:08.360 --> 01:06:16.360
Go for that. Plus 3i. Yeah. What else? Anything else?
730
01:06:16.360 --> 01:06:25.360
2 times n plus 1 times i. You're combining this one and this one?
731
01:06:25.360 --> 01:06:32.360
I'm combining this one and this one?
732
01:06:32.360 --> 01:06:39.360
2i and the 2. You're going to combine this one and this one.
733
01:06:39.360 --> 01:06:45.360
Why don't we do the minus and the 2i and that?
734
01:06:45.360 --> 01:06:59.360
Okay. So there we get n times 2i minus 1. Is that okay?
735
01:06:59.360 --> 01:07:14.360
Do we want that? Okay. So 3i. 2i n. What else is left?
736
01:07:14.360 --> 01:07:21.360
Constance. What's left? Minus n minus 1 and then we got this ugly thing at the end.
737
01:07:21.360 --> 01:07:30.360
Minus 2i squared. Is that okay? Let's double check it. Make sure it's all right.
738
01:07:30.360 --> 01:07:41.360
Let's look at all these pieces. Some of these pieces can still be a little bit more combined.
739
01:07:41.360 --> 01:07:45.360
Let's take these and group them together because they both have i's in them.
740
01:07:45.360 --> 01:07:54.360
3 plus 2n times i minus n minus 1 minus 2i squared.
741
01:07:54.360 --> 01:07:59.360
Now let's look at it and see what we get.
742
01:07:59.360 --> 01:08:07.360
What happens when you add up minus n n times for i equals 1 to n?
743
01:08:07.360 --> 01:08:16.360
There's no i in this picture, right? That means minus n minus n minus n n times.
744
01:08:16.360 --> 01:08:20.360
What does this turn into? Minus n squared.
745
01:08:20.360 --> 01:08:23.360
So easy it is to sum this piece. It doesn't have an i in it.
746
01:08:23.360 --> 01:08:32.360
Start getting used to the following intuition. If you see something inside a summation sign and a piece of it doesn't have this variable in it,
747
01:08:32.360 --> 01:08:39.360
then just multiply it by how many times you're doing it. So here's what happens.
748
01:08:39.360 --> 01:08:48.360
We still have this piece here. i equals 1 to n of 3 plus 2n i.
749
01:08:48.360 --> 01:08:53.360
We still have this piece here that minus 2i squared.
750
01:08:53.360 --> 01:08:59.360
But out here we're going to take the n squared and out here we're going to take what happens to the minus 1?
751
01:08:59.360 --> 01:09:05.360
Minus n because it gets that n times. And that stuff is now out of the summation.
752
01:09:05.360 --> 01:09:17.360
I took it out. It's all been summed. The only thing left to sum is this thing that hasn't i in it and this thing that hasn't i squared in it.
753
01:09:17.360 --> 01:09:24.360
Let's keep going. We're almost done. I should tell you that Levy does not do this with algebra. He does this with words.
754
01:09:24.360 --> 01:09:31.360
So if you can imagine it's hard enough to see this in algebra. If you can get through it in words you really understand it.
755
01:09:31.360 --> 01:09:35.360
We can do the summation that most plus 1.
756
01:09:35.360 --> 01:09:44.360
Before we do that, we are going to do that in just a second. I want you to look at this. What is this whole thing equal? Who remembers?
757
01:09:44.360 --> 01:10:01.360
Who's track? Summation of i squared. What is this? It's the same problem but twice. Here's what we got so far. The summation of i squared equals this.
758
01:10:01.360 --> 01:10:08.360
So I'm going to take the summation of 2i squared and move it to the other side of the equation. I'm going to pull it out.
759
01:10:08.360 --> 01:10:22.360
How many summations do I have here now? Three i squared summations. On this side all I have left is minus n squared minus n.
760
01:10:22.360 --> 01:10:28.360
Everybody see what I did? This is the most clever spot. I'll explain it again. This is the most clever point of the proof.
761
01:10:28.360 --> 01:10:38.360
On this side I have a summation of i squared. In fact I have two of them. They go from i equal 1 to n. That's exactly what the whole formula equals.
762
01:10:38.360 --> 01:10:46.360
So I take this summation of 2i squared and I add it to both sides of the equation. On this side of the equation it cancels this out.
763
01:10:46.360 --> 01:11:08.360
On this side of the equation I get two more summations of i squared.
764
01:11:08.360 --> 01:11:22.360
I'll split these into two different segments so you can see that they're both supposed to be summed up. This one needs to get summed up. Now I'm going to take this and add it to both sides of the equation so it moves to the other side.
765
01:11:22.360 --> 01:11:42.360
On this side gets to be three times the sum of i squared. Other questions about that? If you have two in front of here I can move out right in front.
766
01:11:42.360 --> 01:11:52.360
Each term is multiplied by two so you're just factoring it out. This is the same trick we did with integration by parts for sine and...
767
01:11:52.360 --> 01:12:06.360
Yes, it should remind you of that trick. That's a good point. It's very much like that trick. When you do integration by parts you get the integrals in terms of another integral that's half the size and then you pull it back over and then you get that constant term. That's true. It's just like that trick.
768
01:12:06.360 --> 01:12:18.360
We're almost done here. We got the square root of... We got i squared sum from one to n. We got three of them here. What we have to do is sum this and then we can divide by three and get an answer.
769
01:12:18.360 --> 01:12:32.360
Does this look familiar? The three plus two n is like a constant. That gets multiplied by each one of these i's. Every single time you go from one to n. So it just can get pulled out and factored out.
770
01:12:32.360 --> 01:12:50.360
It does not depend on i. Look at this. Ever see this before? Those are triangle numbers. Adding up i from one to n, one plus two plus three all the way up to n.
771
01:12:50.360 --> 01:13:04.360
Here's what we get. The sum of i squared from one to n times three equals three plus two n. What's the sum of the numbers from one to n?
772
01:13:04.360 --> 01:13:12.360
n times n minus one over two.
773
01:13:12.360 --> 01:13:23.360
n times n plus one over two. I'm almost with you. Right. n times n plus one over two. Thank you.
774
01:13:23.360 --> 01:13:28.360
Good. At least my notes are right.
775
01:13:28.360 --> 01:13:44.360
Three plus two n and n times n plus one over two minus n times n plus one. That's the right hand side here. If you put this over, comment denominator. What do you get?
776
01:13:44.360 --> 01:13:56.360
This is three plus two n times n times n plus one minus two n times n plus one. So it's going to be three plus two n.
777
01:13:56.360 --> 01:14:10.360
Three plus two n minus two times n times n plus one over two. Three plus two n minus two is the same as two n plus one.
778
01:14:10.360 --> 01:14:28.360
If I divide through by three, I get a six here. The final answer is two n plus one n plus one n divided by six.
779
01:14:28.360 --> 01:14:39.360
That is the same as the way it's written there. That's a long, long, long manipulation of a sum. It's a great example of manipulating sums.
780
01:14:39.360 --> 01:14:48.360
There's nothing in this manipulation that doesn't consist of the following things. If you get the sum of lots of things, you can split them into the sums of the pieces when they're added or subtracted together.
781
01:14:48.360 --> 01:14:57.360
If you get a constant or something that doesn't depend on I on the inside of your sum, you can pull it out in front of the sum as if you're factoring it.
782
01:14:57.360 --> 01:15:10.360
All of these symbolic things you have to get used to are just transferences from what you do in algebra. But think about it intuitively and stop making the intellectual connection.
783
01:15:10.360 --> 01:15:19.360
When you stop making the intellectual connection, you immediately get used to the fact that if I see pieces multiplied inside the sum and there's no eyes in those pieces, I can pull them out.
784
01:15:19.360 --> 01:15:26.360
If I see lots of pieces inside the sum that are pluses or minuses together, I can split them into smaller pieces.
785
01:15:26.360 --> 01:15:39.360
Get used to those manipulation rules and you'll be able to work faster with these summation signs than you will with a dot dot dot notation.
786
01:15:39.360 --> 01:15:47.360
All right, questions about any of this? That's a good question.
787
01:15:47.360 --> 01:15:56.360
There's actually no complicated idea here except for the notation of the sum. Maybe Sam will go over this in recitation today at 4.
788
01:15:56.360 --> 01:15:59.360
What do we say? 4.
789
01:15:59.360 --> 01:16:02.360
Get into the sum notation.
790
01:16:02.360 --> 01:16:04.360
You mean writing it like this and making?
791
01:16:04.360 --> 01:16:08.360
Going from the original one plus two.
792
01:16:08.360 --> 01:16:19.360
That's the hardest part. That's the hardest part. If you can't manipulate the sum at all, that's the most important thing.
793
01:16:19.360 --> 01:16:26.360
If Sam goes over this slowly at 4 o'clock today, anybody who didn't get it here would benefit a lot. It's important to get good at this kind of thing.
794
01:16:26.360 --> 01:16:31.360
If this seems like a lecture from the clouds in the last 20 minutes, then definitely go see it again.
795
01:16:31.360 --> 01:16:46.360
I got it. It's online. Yeah. Yeah, I can't always say that, but today I can. Let me think. Wait, did I really do it?
796
01:16:46.360 --> 01:16:53.360
I probably did. I got to go check on. I'm not sure how far I am in typing my lecture notes, but they might be there. They're certainly written here yet.
797
01:16:53.360 --> 01:17:05.360
Is this how to work with infinite sums? Yes. Well, Tara is going to do a bunch of infinite sums in the recitation. I'm going to do some infinite sums.
798
01:17:05.360 --> 01:17:10.360
I didn't get to where I wanted to. I'm right on time, but I didn't get ahead of myself today.
799
01:17:10.360 --> 01:17:13.360
The next thing I wanted to do is move over to recursion and recurrence equations.
800
01:17:13.360 --> 01:17:25.360
The first thing we're going to do is that Tara's of a newy problem that you did last month. In doing that, we're going to come up with a sum that will be an infinite sum, or at least looks like an infinite sum.
801
01:17:25.360 --> 01:17:33.360
We'll cut it short at some point and make it finite. I'll show you how to add up geometric sums. From geometric sums, we'll do things that are similar to that.
802
01:17:33.360 --> 01:17:44.360
Let me take a picture. This is the sum of the squares. You did triadle numbers. You did a divergent and convergent series two months ago. All those things are part of summations, but it's a big, big topic.
803
01:17:44.360 --> 01:17:53.360
I'm just going to throw in the basics in the next couple days. We're going to do geometric series and versions of geometric series, which you glid new 2,000 years ago.
804
01:17:53.360 --> 01:18:03.360
That's old stuff. Then, as we move into Tara's of a newy into other recursive stuff like your seven rings problem, we're going to come up with a sum of the squares.