0:00
[SQUEAKING] [RUSTLING] [CLICKING]
0:12
CASEY RODRIGUEZ: OK. So I have to admit this is extremely awkward,
0:19
lecturing to an empty room. So I have to imagine there’s somebody on the other end actually listening to me at some point.
0:26
Perhaps this is what YouTube stars have to go through
0:32
at some point in their career. So what is the purpose of this course?
0:38
So this is for 18 100A, Real Analysis.
0:51
So the purpose of this course is twofold.
1:03
Really, I think the first primary purpose of this course is to gain experience with proofs.
1:16
So that means being able to read a proof,
1:23
being able to write a proof. And the second statement, or the second purpose,
1:31
which is supposed to be a way to obtain the first purpose,
1:37
is to prove statements about real numbers, functions,
1:57
and limits.
2:07
OK. So the second part, this is the analysis part, OK?
2:21
So for the first few lectures, we’re going to do what maybe to some will be kind of review.
2:30
And for most of you, a lot of this material in the first few lectures will be review.
2:40
But it’s a nice way to ease into the material. And things will most definitely pick up after a few lectures.
2:49
So the first set of objects we’re
2:56
going to define and try to prove some statements about are sets. So definition— and because I use a lot of shorthand,
3:12
I will mostly write Dfn from now on instead of the entire word, definition.
3:18
So a set is a collection of objects
3:39
called elements or members, OK?
3:47
Now, this course is supposed to be
3:54
probably the first really rigorous course in math that many of you will deal with.
4:01
So essentially, everything that we talk about will be rigorously and unambiguously defined.
4:09
But we do have to start somewhere. And so maybe you think this word,
4:16
“collection,” is a little ambiguous. And perhaps you should.
4:22
But to actually build up set theory from the ground up
4:28
would take us quite beyond the scope of this class and too far
4:34
afield of the things that we want to do, or at least that what I want to do.
4:41
OK, so a set is just a collection of objects called elements, or members.
4:48
There is the simplest set to define:
4:55
the empty set is the set with no elements.
5:06
And we denote it by this symbol here— a circle with a dash
5:16
through it.
5:22
OK, so with new math typically comes new notation, new symbols that you use.
5:29
So let me introduce a few shorthand notations we’ll use throughout the course.
5:37
I mean, quite honestly, this is a little bit of the fun of doing higher math.
5:42
You get all these funny symbols. And a very accomplished mathematician
5:48
at the University of Chicago, one time said, you’re really only interested in the math
5:54
where that has the symbols you like to write over and over again.
5:59
So some notation— a and this symbol which this symbol, which looks like a e-S
6:07
means a is an element of S. A with a dash
6:22
through this little e means everything here but.
6:30
So a is not an element of S.
6:36
This upside down A means for all.
6:41
It’s shorthand for all. Backwards E means there exists.
6:51
And a couple of more— if you see an arrow like this, this means implies.
7:05
So I’ve written down one thing. This implies the next statement. I’ll put an arrow between them.
7:12
And an arrow going both ways means if and only
7:21
if, meaning if I have a statement P if and only if Q, that means statement P implies Q and statement Q implies
7:31
P, all right? And if you need a quick refresher on basic logic,
7:39
you can find that in the appendix of the textbook.
7:46
OK, so that’s the basic definition of set, empty set.
7:54
So set A— another definition to set
8:04
A is subset of B, which we write A, this little symbol
8:17
that looks like a C, B If every element in A
8:26
is an element in B. Little a’s in capital A means little a is in capital B.
8:39
So two sets are equal—
8:48
we write A equals B— if A is a subset of B and B is a subset of A.
9:15
And A is a proper subset of B if A is a subset of B
9:29
and A does not equal B. And we typically
9:36
write that by A and with a dash going through a line underneath the C to signify that it’s not equal.
9:45
So think of it as not, so less than or equal to, but not equal to is one way to think about it.
9:52
OK, so let me say something since I’m now
10:02
1, 2, 3 definitions in. So definitions are a fact of life when it comes to math.
10:09
In the beginning of any subject, there’s going to be a lot of definitions because we have to have objects we want to talk about.
10:16
And we have to have these unambiguously defined objects. So it may seem like there’s going
10:24
to be a lot of definitions now, but this will let up. And we will start proving some theorems, which
10:30
are facts, about these objects. These are the things that we’re really after.
10:36
We’re not really after just making up definitions. Definitions are meant to be a rigorous way
10:45
of defining an object we’re interested in studying. We’re interested in proving theorems, facts about them.
10:52
So again, a lot of this is just probably review.
11:01
11:09
When we describe sets, we will use these braces
11:19
and maybe list the elements in here. Or we will describe it as x in some set A,
11:29
satisfying some property P of x.
11:34
Or we won’t write this x and A part. We’ll just write all objects x satisfying
11:42
x, as being an element of whatever universe we’re in,
11:47
that satisfy property P of x, OK? So again, you should read this as all satisfying property
11:58
P of x. So the basic examples—
12:07
and this is— you should expect this after seeing any non-trivial definition.
12:14
If you were here, I would ask you to call me out, so I’ll have to police myself.
12:19
But after every semi-interesting definition,
12:24
you should see examples, OK? This is how you actually learn about these things,
12:31
or at least digest what these things are. So we have the natural numbers, which everyone is familiar with since they started to count—
12:37
1, 2, 3, 4, and so on. We have the integers, which is 0, 1, minus 1, 2, minus 2.
12:49
So all the natural numbers, along with their additive inverses, along with the 0 element, an additive identity, we have the rational numbers.
13:01
So this is written as m over n such that m and n are integers
13:10
and n does not equal to 0.
13:15
And we have R, the real numbers, which I, as of right now,
13:29
cannot actually write down what they are in terms of set-building notation.
13:36
In fact, this will be our first goal of the course, is to give a proper description or definition of what
13:44
R actually is.
13:49
But you can think of this as you did in calculus,
13:55
as Q along with—
14:01
so rationals and irrationals, like pi and 2 and these things.
14:09
So this is fine to think about for now.
14:17
So of course, I didn’t have to use these.
14:27
Maybe I’m interested in odd numbers. That’s a set of numbers of the form 2m minus 1,
14:34
where m is a natural number. So this is just 1, 3, 5, and so on, OK?
14:44
And so note that we have the inclusions.
14:49
Natural numbers are contained in the integers, which are contained in the rational numbers, which are contained
14:55
in the real numbers, OK? And if you look at the history of why these things were
15:03
thought up in the first place, I mean, they were thought up to solve polynomial equations
15:11
that you couldn’t solve in the number system before. Integers were created because I could not
15:17
solve the equation x plus 1 equals 0 in the natural numbers.
15:23
Rationals were thought of because I could not solve the equation 2x plus 1 equals 0 in the integers.
15:31
And the real numbers were thought of because I cannot solve the equation x squared minus 2 equals 0
15:37
in the rational numbers. Now, I can’t solve the equation x squared plus 1 equals 0
15:43
in the real numbers, which led to the creation
15:48
of complex numbers. But we will not deal with complex numbers in this class. Although hopefully, if you keep studying analysis,
15:55
you go on to complex analysis, which is really a beautiful subject of study to this day.
16:07
So as I said— let me write this here—
16:14
our first goal, real goal of the class— and this is something to keep in mind.
16:19
We’re not going to do it right now. Our first real goal is to describe what R is, OK?
16:36
I mean, if we’re going to be proving statements about the real numbers, functions of real numbers, and limits,
16:42
whatever— those limits that you learned in calculus— then we have to be able to really describe
16:49
what we’re starting with, the real numbers.
16:55
OK, so let’s get back to sets, to our review of sets.
17:00
So there were some examples.
17:06
We have a few more definitions.
17:14
The union of two sets, A and B, is the set which we write—
17:24
so this is how we denote it, A U B. This
17:30
is the set of all elements x. x is in A or x is in B.
17:49
The intersection of A and B— so this was defining the union.
17:56
This was defining the intersection—
18:02
is the set A cap B. And this is a set of all
18:10
x’s so that x is in A and x is in B.
18:23
So the union is take all the things from A, take all the things from B, and put them together
18:29
in one big basket. The intersection is just take the things that A and B have in common.
18:35
The set difference of A with respect to B
18:53
is the set A backslash B. This is
19:05
the set of all elements in A such that x is not in B. The complement of A is the set A—
19:28
so this is how I’m denoting the set. The next part is how I’m defining the set.
19:34
This is a set of all elements in our universe that is not in A.
19:44
And when I say universe, I don’t mean this universe necessarily.
19:50
I mean, if we’re looking at subsets of R, the complement is generally with respect to R.
20:00
Or if all of our sets are subsets of Q, then our universe would be Q, the rationals.
20:06
And we’re taking the complement in there.
20:12
Two sets are disjoint if their intersection is empty, OK?
20:28
So it took me quite a long time to figure out
20:35
this compliment has an E in the middle as opposed to an I, as in the compliment you would give a friend.
20:42
I had to do a lot of spell-checking in my thesis
20:47
when my advisor pointed that out. So this is just something to keep in mind. This complement has an E in the middle of it.
20:54
OK, so let me just draw a quick picture.
21:05
So this blob over here is A. This is a set B. This is a set C. In fact, let’s
21:15
make this a little more— OK, let’s keep C there. Then what I have here, that’s A intersect B. This bit
21:29
over here, with the lines going this way but not including this, this is A take away B, A backslash B.
21:38
And OK, so that was not meant to be
21:45
along the same direction as this one, so let’s go vertical. And everything with a vertical line is A intersect B, OK?
21:59
So A backslash has the lines going this direction.
22:04
A intersect has the lines going this direction.
22:10
A union B has the lines going vertical. And C is way over here not touching any of A and B.
22:18
So A and C are disjoint and B and C are disjoint.
22:33
OK, they have nothing in common.
22:38
22:44
OK, so this was a lot of definitions.
22:54
We have not proven a single statement yet, so it’s about time we do. This is probably one of the most basic theorems
23:03
one can prove at the start of a Real Analysis class or any class about proofs.
23:09
This is analogous to when you write your first Hello World
23:14
program in a programming class. So let me state the theorem, which is DeMorgan’s Laws.
23:30
And the statement is the following. So if A, B, C are sets, then I have several things I can say.
23:46
23:51
The union of B and C, taking their complement, this is the intersection of the complements.
24:00
So the complement of the union is the intersection of the compliments.
24:06
If I take their intersection and take the complement, this is the union of the complements.
24:14
So the complement of the intersection is the union of the complements.
24:21
Now, these are complements, meaning I am, in some sense, taking a set difference with respect to the entire universe.
24:27
But I can make these things relative to some set A. So A take away B union C, this is the same
24:36
as A take away B intersect A take away C. Really, again,
24:45
you should think of this as a special case of one.
24:51
Or at least if you were to write the proof— I’m not going to because it’s all
24:56
going to be contained in the first two— then you would see it’s really just a proof of this guy.
25:03
A take away B intersects C equals A take away B union A
25:12
take away C, OK? So again, for a quick refresher about logic
25:22
I would look at the appendix of the textbook. In general, so let me make a few remarks
25:30
before we move on to the proof about typically how this is going to look.
25:35
So this is some remarks.
25:40
Typically, a theorem is a statement
25:47
of the type P implies Q. Let me write this out in English. If some statement P holds, then Q—
25:56
for us, it’s if I have any three sets, then I have these equalities between these operations
26:03
of sets.
26:08
So the general structure you’ll see of the class is I have objects which I define unambiguously.
26:13
I want to prove theorems now, meaning true statements about these objects. And the real meat is the proof part.
26:21
So what is in this mysterious guy, the proof?
26:28
It’s quite simple. You start with— you assume P, meaning what you were given,
26:43
the hypotheses, the hypothesis, P, and—
26:49
I’m going to put dots here— through logic and most
27:00
definitely, most of the time some calculations, you arrive at Q is true.
27:12
And most proofs are ended with this little box here, OK? So most proofs have this structure.
27:22
I take my hypotheses. And these hypotheses mean something
27:30
in terms of the definitions I have given. And now, I need to use these unambiguous definitions,
27:38
along with logic and maybe some calculations, to conclude that statement Q is true.
27:45
That is the essence of a proof. That is all there is to it.
27:54
Now, that doesn’t mean it’s a simple thing to learn how to do. That’s the point of this course.
28:00
But distilled down, that’s what a proof is, OK?
28:06
And Q— so I said P usually means something in terms
28:11
of the definitions we have. But also, Q will usually mean something in the definitions that we’ve given.
28:17
And so our job is to verify Q. So let’s
28:22
go with proving this theorem.
28:28
And in fact, I’m only going to prove property 1. Property 2, 3, and 4 I’ll likely put on the homework.
28:37
So let B and C be sets.
28:44
So I mean, this is the only hypothesis I get. I’m trying to prove that B union C
28:50
complement equals the intersection of the complements. So what does that mean?
28:55
So we want to prove. So this is— it’s quite helpful, especially
29:04
when you’re first starting to do proofs, to write down what you’re actually trying to prove. So even though I have this statement here,
29:13
it’s an equality between two sets. Equality between two sets means something specifically, right?
29:20
We have that in our definition— where is it— over there that two sets
29:28
are equal if one is a subset of the other and vice versa. So that’s what we have to prove.
29:34
We have to prove that the left side, B union C complement, is a subset of B complement intersect C complement and vice
29:42
versa. So we want to prove that is a subset of B and—
29:56
30:05
OK? So that’s what the equality means.
30:11
That’s what we have to prove. We have to prove those two statements now, OK? And that’s as distilled down as far as we can go.
30:18
So let’s prove this. Now, we’ll prove this using, again, logic and what
30:27
these things actually are. So let’s prove this first statement here.
30:35
So I have to show that every element in this set is an element of this set.
30:42
So I’ll even write this down as WTS.
30:49
That means Want To Show. This is the first thing we’ll show.
30:56
As we go on, I’m not going to write as much as I’m doing right now. But this is the first theorem and proof you’re seeing,
31:03
so I should write down quite a bit. So the first thing we want to show
31:08
is we have this inclusion, OK? That means every element here is an element here.
31:13
So let x be in B union C complement.
31:22
And now, we’re going to trace what this means. And we’ll eventually arrive at x as in this.
31:28
So then x is not in B union C. That’s just
31:36
the definition of the complement. Now, x is not in B union C means x is not in B and x is not in C
31:51
because the union is— something’s in the union if it’s in B or C. So something’s not in the union if it’s not in B and not in C.
32:02
Now, this implies, simply again by the definition of what it means to be in the complement,
32:09
x is in B complement and x is in C complement.
32:15
But this, again, is simply the definition
32:23
of x being in B complement intersect C complement, OK?
32:31
So you see, we started off with an element in this guy and we showed that it’s also an element of the right-hand side.
32:41
So thus, B union C complement is contained in B complement
32:51
intersect C complement. Now, we want to do this other inclusion here.
32:56
33:10
Now, this is one of those rare situations where
33:16
you get to essentially reverse the entire argument and get what you want.
33:25
But let’s just go through it in a linear fashion.
33:33
Let’s take something from here and show it’s in here.
33:38
So let x be in the intersection of the complements. Then that means x is in B complement
33:48
and x is in C complement. That means x is not in B—
33:58
so that’s this statement. That’s the definition of being in the complement— and x is not in C. That’s, again,
34:07
the definition of being in the complement. Now, just like we used here in this step,
34:14
this is equivalent to— so really, I should— in this statement, I should have written
34:21
this statement is equivalent to this statement, but we’ll remove that.
34:26
So x is not in B and x is not in C. This means x is not in their union, which
34:36
implies that x is in the complement of the union, OK?
34:46
So thus, we’ve proven is a subset of B.
35:00
And since we’ve shown both sets are
35:05
a subset of each other, that means, by the definition of two sets being equal, they are equal.
35:12
35:21
Again, this box means really nothing. It just means that’s the end of the proof.
35:40
All right, let’s move over here.
35:47
35:54
This is terrible.
36:10
And not everybody uses that little box to finish a proof.
36:15
Some people don’t put anything. When I was in graduate school, I was a TA for this guy named Paul Sally who
36:25
was a fantastic teacher and really loved math,
36:32
who would end— So amazing story about this guy is, when I was his TA,
36:40
he was in his 70s, I think. But he had also had diabetes.
36:47
So he had lost both of his legs beneath his knees.
36:52
He was also legally blind. And he had a patch over one eye.
36:58
So he himself often referred to himself as the a pirate mathematician.
37:06
But he would end his proofs with— at least in his textbook— he didn’t
37:13
ask me to do this on the board, thankfully. He would end his proofs with a picture of himself
37:22
with this cob pipe that he had, very much
37:27
in the pirate fashion. Anyways, OK, moving on from things that end proofs,
37:35
let’s go on to a next subject, induction.
37:45
So induction is a way to prove theorems about natural numbers,
37:53
OK? The theorem itself is more of a tool rather
38:01
than an interesting fact on its own, OK?
38:07
So let me state the theorem. And then we’ll go over a couple of examples on how to use induction.
38:13
So let me recall from—
38:20
I think I just erased it. N is the natural numbers.
38:27
And it has an ordering, meaning—
38:33
so we’ll precisely define what ordering means. But just in your head, this means the usual thing—
38:39
1 is less than 2 is less than 3 is less than 4.
38:47
So a property of the natural numbers, which will take as an axiom, is the well-ordering property.
38:56
39:07
So an axiom is not something you prove. You assume this about the objects
39:13
that you’ve defined or are studying up to this point.
39:19
And so the statement is if I take
39:26
a subset of natural numbers, which is non-empty,
39:33
then S has a least element or smallest element.
39:44
Now, what does this mean? Let me write this last statement out.
39:50
i.e. There exists an x in S—
39:56
“st” I will often write, meaning such that or so that— such that x is less than or equal to y for all y in S, OK?
40:11
So every non-empty subset of the natural numbers has a smallest element, OK?
40:19
We’re going to take that as an axiom, as just a property of the natural numbers, which
40:25
we’ll assume. Now, using this axiom, we’re going to prove—
40:32
it’s not really often you hear it called as a principle of mathematical induction,
40:38
but this will state it as a theorem instead of a principle, whatever a principle is supposed to be. So induction, so this is due to Pascal.
41:00
Or at least in its first rigorous formulation is let Pn be a statement depending on natural number n.
41:26
OK, so maybe we have some equality between two quantities that involves a natural number n,
41:32
OK? That could be our statement P of n. Now, we’re going to assume—
41:40
so what are our hypotheses about this statement? What’s our if?
41:46
Assume that this statement satisfies two properties.
41:51
This first property is usually referred to as a base case.
42:01
That is that P of 1 is true. And the second property is called the inductive step.
42:10
42:18
So this statement satisfies the following property
42:24
that if you assume P of m is true,
42:31
then you can prove that P of m plus 1 is true.
42:39
So I have a statement which satisfies both of these properties, OK? In particular, since I’m assuming P of 1 is true,
42:47
by the second property, P of 2 is true. And then again by the second property, P of 3 is true.
42:53
And then P of 4, and then P of 5. And so if you followed that last line of reasoning,
42:59
this means you should be able to guess what the conclusion of this theorem is.
43:06
Then P n is true for all natural numbers, OK?
43:21
All right, so we’re going to use the well-ordering property of the natural numbers to prove this theorem
43:31
about the induction. OK, so we have our assumptions.
43:41
I’m not going to— although, I said over there let B, C be sets, I’m not going to rewrite the assumptions that we have about our statement
43:48
P. We’re just going to start trying to prove P of n is true for all n.
43:54
So let me write our conclusion slightly differently.
44:02
Let S be the set of all natural numbers such that P of n
44:15
is not true. So what I want to show is that P of n is true for all n.
44:20
So that’s equivalent to saying we want
44:26
to show that S is empty, OK?
44:34
The set of natural numbers where P of n is not true, this is empty. This is equivalent to saying P of n is true for all n.
44:42
And the way we’re going to do this is another staple of mathematical proofs
44:57
is trying to prove this by contradiction, OK?
45:12
So what does that mean? Let me make a few comments about what that means,
45:21
proof by a contradiction.
46:01
OK, so in a proof by contradiction— so this is— what I’m about to write down
46:07
is not part of the proof. This is commentary not to be included in the proof.
46:13
What does it mean to say we’re going to prove S is equal to the empty set by contradiction?
46:23
We’re going to assume that the statement we want to prove
46:28
is false. Or not false, but we want to assume that the negation of the statement we want to prove
46:37
is true and then arrive at a false statement, OK?
46:43
So we want to assume— this is what we’re going to do.
46:48
We’re going to assume the negation of the statement we want to prove— namely, S is non-empty, OK?
46:58
And from this, we want to derive a false statement, OK?
47:14
And so if we are to do— if we were able to do that, then—
47:22
let me just say, again, you can check in the appendix or you can just believe me that the rules of logic
47:34
then say that our initial assumption, that S was not
47:48
empty, is false to begin with, OK? So rules of logic, meaning I cannot start from a true
47:56
assumption and derive, in a logically consistent way,
48:02
a false statement, OK? That is, if we believe that the rules of logic we’re using
48:09
are consistent, which that’s a little bit hairy to talk about.
48:19
But for our purposes of our class,
48:24
you can believe me that the rules of logic we use— or at least accept that the rules
48:30
of logic we’re going to use are consistent and sound.
48:36
OK, so back to the proof at hand. We have this set of natural numbers
48:42
where the statement is not true. We want to show it is empty. We’re going to do it by contradiction, meaning
48:48
we’re going to assume the negation of the statement we want to prove— namely, S is non-empty. And we’re going to derive a false statement
48:55
from that assumption, OK? And by the rules of logic— that means that our initial assumption—
49:02
that S is non-empty— is, in fact, false, OK?
49:09
All right, so towards a contradiction,
49:16
suppose that S is non-empty, OK? Now, we’re going to use the well-ordering property
49:23
of the natural numbers. By the well-ordering property of the natural numbers,
49:37
S has a least element, x, OK?
49:48
Now, what do we know about x?
49:58
So first off, x cannot be 1, OK? S is a set where this property does not hold.
50:03
x cannot be 1 because— let me again rewrite this fact that S has the least element.
50:13
Let me just reiterate that S has a least element in the set, OK?
50:18
Now, x cannot be 1 because we’re assuming the base case, meaning P of 1 is true.
50:24
So since P of 1 is true, that means 1 is not
50:34
an S, which means x is not 1.
50:39
50:45
In particular, x must be bigger than 1. So x is some magical natural number out there bigger than 1
50:51
that’s the least element of this set S.
50:56
OK, since x is the least element of S—
51:09
so let me draw.
51:15
On the number line, we have 1, 2, 3, 4. Out there is some magic point x, which
51:21
is the least element of S. And the rest of the subset S lies to the right of this number x, right?
51:30
Because it’s the least element of S. And therefore, x minus 1 cannot be in S.
51:41
So since x is the least element of S and x minus 1 is less than
51:49
x, this means that x minus 1 is not in S. Otherwise,
51:56
it would be a smaller element than x in S. So thus,
52:05
what does it mean to not be in S? It means that P of x minus 1 is true.
52:11
By the definition of S, this means P of x minus 1
52:20
is true, OK?
52:27
But by the second property we’re assuming about our statement P,
52:36
this means that the next guy in line, x minus 1 plus 1,
52:44
is true, which is just x, which means that x is not in S, OK?
52:58
So from the assumption— so let me just recap.
53:04
From the assumption that S is non-empty, we’ve derived two facts. 1, x has the least element in S. And that element is also not
53:16
in S. So written out, we’ve concluded there
53:34
exists a natural number which is both in S and not in S.
53:41
And this is a false statement. You cannot have an object and member that’s both in the set
53:48
and not in the set, OK? And at the end of contradiction arguments,
53:56
I’ll usually put two arrows hitting each other. So that’s a contradiction. Therefore, our initial assumption that S is non-empty
54:03
has to be false.
54:10
And therefore, S is the empty set, OK?
54:16
So I encourage you to go through that proof a little slowly because maybe you got turned around
54:24
by taking the complements or the general scheme of how
54:30
a proof by contradiction works. But don’t spend too much time on it because, as I’ve said,
54:40
this theorem itself and its proof are not the thing we’re really interested in. Or at least, it’s not the most interesting.
54:47
It’s more of a tool that we’ll use to prove more interesting statements.
54:53
OK, so how do we actually use this theorem, induction, to prove other statements?
54:59
So I guess I should include this here. This falls under the umbrella of logic,
55:06
meaning we’re going to approve previous— we’re going to use previous statements we’ve proven to prove new statements.
55:13
But anyway, so how do we use induction in practice?
55:27
So if we want to prove some statement—
55:34
55:39
for all n, Pn is true—
55:44
in the print then, this theorem about induction— this theorem of induction— tells us
55:49
we just have to do two things, OK?
56:02
We have to prove the base case.
56:08
And this is usually easy. You just stick the number 1 into the statement
56:14
that you want to prove. And that’s the end of the story.
56:21
56:27
And the second step is usually— or the second thing we have to prove is the more involved part, which is
56:33
we have to prove that the statement that if PM is true,
56:50
then P of m plus 1 is true, OK?
56:56
If we want to do a proof by induction, there’s two smaller proofs we have to do. First, we have to prove P of 1 is true.
57:04
And then we have to prove this statement. If P of m, then P of m plus 1.
57:09
So again, this is usually referred to as the base case.
57:15
This is the inductive step. So let’s try and actually do this.
57:29
All right, so— so another question I get at the beginning
57:39
of a course, especially about proofs— because there’s a lot of uncertainty about what you
57:45
can assume is true, what can you use, what can you not use, right now, at this point, you
57:51
can use whatever you know about any
57:57
of the algebraic properties, you know about the real numbers, the rational numbers—
58:02
and by algebraic properties, I mean if a plus b equals
58:08
c, then a plus b times d equals c times d— and what you know about inequalities.
58:16
So we’re going to go much more in depth into ordering, which is what inequality is a part of.
58:27
But you can use all the properties you know about solving inequalities or manipulating
58:33
inequalities, meaning if I have one number is less than or equal to another number, then when I multiply
58:39
both sides by a positive number, that doesn’t change the inequality. So you can use all of these algebraic properties
58:48
of rationals and real numbers from here on out.
58:55
I mean, so we’re going to be proving things about calculus. So you certainly cannot use anything about continuity,
59:03
differentiation, or anything like that. But for now, you can use all the algebraic properties you know.
59:12
So the first statement we’re going to try and prove using induction is the statement that for all c not equal
59:24
to 1, for all n, a natural number, 1
59:30
plus c plus c squared plus c to the n equals 1 minus c to the n
59:37
plus 1 over 1 minus c, OK? So this here is our statement P of n.
59:49
It depends on the natural number n, OK? So we’re going to do this by induction, which means we’re
59:57
going to do those two things. We’re going to prove the base case, P of 1, which I said is easy.
1:00:02
And then we’re going to prove the second case, the second property, the inductive step, which is a little more involved, but not so much involved,
1:00:12
at least in the beginning. So let me call this inequality star.
1:00:19
1:00:27
We’re going to prove star by induction. So first, we will do the base case.
1:00:35
1:00:41
And like I said, the base case is usually you
1:00:46
just plug in n equals 1 and verify that P of n is true. And that’s what we do.
1:00:53
1 plus c to the 1, which is the left-hand side, does, in fact, equal 1 minus c to the 1 plus 1 over 1 minus c because this
1:01:05
right-hand side—
1:01:11
1 minus c squared is 1 minus c times 1 plus c—
1:01:17
the 1 minus c’s cancel. And so the base case is proven, all right?
1:01:26
1:01:31
Now, we do the inductive step, OK?
1:01:41
So we’re going to assume that star holds for n equals m
1:01:47
So we’re going to assume P of m. So assume that 1 plus c plus c to the m
1:01:57
equals 1 minus c over 1 minus c, OK?
1:02:04
Now, we want to show— again, let’s write out what we want to do, what’s our plan.
1:02:11
We want to prove that this equality, that this line
1:02:22
star holds for n equals m plus 1, OK?
1:02:33
So again, what I wrote here, this is basically star for n equals m, OK?
1:02:47
And let me call this second inequality— the second equality 2 star.
1:02:53
So this is my assumption for m, n equals m.
1:03:00
OK, so let’s take the left side for n equals m plus 1 and see
1:03:09
if we cannot massage it to get the right-hand side for—
1:03:15
I should say the right-hand side for n equals m plus 1.
1:03:23
So here is the calculation part. So we have 1 plus c plus c to the m plus c to the m plus 1.
1:03:33
This is the m plus 1 case of the left-hand side of star,
1:03:38
which we want to show is to the— is equal to the n equals n plus 1 case of the right-hand side.
1:03:46
Now, this is equal to— now, we already know what this is equal to by our assumption.
1:03:53
This is by the second star there, which is what we’re assuming is true.
1:03:59
This is equal to 1 minus c n plus 1 over 1 minus c plus cm plus 1.
1:04:12
And so now, we just do a little bit of algebra. This is equal to 1 over 1 minus c
1:04:18
m plus 1 plus c m plus 1 minus c m plus 2 over 1 minus c.
1:04:27
Those cancel and I’m left with 1 minus c to the m plus 2. And I’ll write it just so that you can see this is really
1:04:36
the m plus 1 case, all right?
1:04:46
So again, we arrived at this first step
1:04:51
by our assumption, the second starred equation, OK?
1:04:57
So thus, star holds for n equals m plus 1.
1:05:10
So by induction— or really, I should say the theorem
1:05:17
of induction that we proved—
1:05:23
our equality between those two objects, or two expressions,
1:05:29
is valid for all n, OK?
1:05:38
1:05:58
OK.
1:06:50
OK, so let’s do one more example of using induction.
1:06:59
So let’s prove if C is a real number bigger
1:07:07
than or equal to minus 1, then for all n,
1:07:16
a natural number, 1 plus c to the n
1:07:22
is bigger than or equal to 1 plus n times c, OK?
1:07:30
All right, so we’re going to do this by induction again.
1:07:37
That means we need to prove the base case and we need to do the inductive step.
1:07:43
So base case, as always, will— so this is just right here. We’re going to do this by induction.
1:07:52
So as you can see, the base case is,
1:08:00
again, n equals 1 is clear just by looking at it.
1:08:05
1 plus c to the 1, in fact, equals 1 plus 1 times c.
1:08:12
So it’s certainly bigger than or equal to 1 plus n times c. So I think that’s the last stars I’ll use for this lecture.
1:08:28
So our statement, our inequality star star star,
1:08:37
holds for n equals 1. All right, so that’s our base case.
1:08:42
Now, we’re going to assume that this inequality holds for n equals m and try to prove that it
1:08:49
holds for n equals m plus 1.
1:08:59
So we’re assuming this when n equals m.
1:09:05
So 1 plus c to the m is bigger than or equal to 1 plus m times
1:09:12
c. And we want to prove this inequality with n
1:09:19
equal to m plus 1. And we’re just assuming this guy, OK?
1:09:26
So I want to get the statement for n equals m plus 1. One way to do that is this left side.
1:09:34
I want to get— let’s look at the n equals m plus 1 side
1:09:40
and see what we can do with it. So again, this is a calculation part and logic.
1:09:47
So we have 1 plus c to the m plus 1. So that’s the n equals m plus 1 side of this.
1:09:55
This is equal to 1 plus c times 1 plus c to the m.
1:10:03
Now, we’re assuming, again, this inequality. This is the n equals m case.
1:10:09
So we can use it. So we’re assuming it. We use it. And since C is bigger than or equal to minus 1, 1 plus C
1:10:17
is non-negative. So this thing is bigger than or equal to this thing.
1:10:22
So if I multiply both sides by 1 plus c, I preserve the inequality. So this is bigger than or equal to 1 plus mc, OK?
1:10:37
Again, this just follows from essentially the assumption multiplied through by 1 plus c, OK?
1:10:44
So now, I’m going to finagle this.
1:10:56
So let me just—
1:11:01
I’m not doing anything different here. I’m just going to rewrite this over here so that I can have a chain of inequality.
1:11:12
So I have 1 plus c to the m plus 1 is greater than or equal to 1 plus c 1 plus mc.
1:11:20
All right, so now, this is bigger than or equal to this. And this here— so when I write equal,
1:11:27
I do not mean that this left side is now equal to what I’m about to write here. That means the previous thing on here is equal to what I’m about
1:11:36
to write here, OK/ this is a typical fashion and writing
1:11:46
down inequalities— or I guess, practice. So this is equal to 1—
1:11:51
so just doing the algebra— m plus 1 times c plus m times c squared, OK?
1:12:01
Now, this part is exactly the n equals m plus 1 side of this.
1:12:07
And I have a little room to give because now this
1:12:13
is plus something that’s non-negative.
1:12:21
So let me just rewrite this again. This means that 1 plus c to the m plus 1
1:12:27
is greater than or equal to 1 plus—
1:12:34
so again, I’m kind of writing a lot here. I will stop writing as much as the course goes on.
1:12:40
But I encourage you, especially in the beginning,
1:12:46
to write all the steps and logic, OK?
1:12:53
So again, I’m not rewriting anything. I’m just summarizing what I’ve done here.
1:13:01
Now, this right-hand side— so I have this as bigger than or equal to this. And this right-hand side, since I
1:13:07
have a number plus something non-negative, m times c squared— m’s a natural number. This is bigger than or equal to 1 m plus 1 times c.
1:13:19
Thus, 1 plus c to the m plus 1 is greater than or equal to,
1:13:30
which is the n equals n plus 1 case.
1:13:46
So by induction, this inequality triple star holds for all n.
1:13:58
1:14:13
All right.