Hello everyone. Welcome to week 3 of Carmen's Core Concepts. Again in these videos, we go over the current week in Math 135 and just give you a little bit of a highlight reel of what you did this week, and hopefully how… it's just a summary of what we did this week. Again reminder that this isn't a substitute for going to lectures, I'm definitely going to go a lot faster than in lectures and only cover really key points. The other thing of course, this also isn't substitute for actually doing the math, right? Just like if I watch a swimmer swim, doesn't make me a good swimmer. Watching me do math, doesn't make you a good mathematician. You have to actually go out and do mathematics.
On that note, let's take a look at the table of contents for the week. So again, if you look at this table of contents and you see a topic that you like, just go to that approximate minute in the video. Scale it as appropriate, and you can watch that clip. So we're going to start off with translation from mathematics to English so how to actually read and write things from English to math and math to English. We talked about contrapositive, different types of implications, contradiction, uniqueness, we also spent a little bit time talking about functions, so injections and surjections, we talked about the division algorithm, and for my class I finished with summation and product notation. I also finished on Friday with a bunch of random examples, which you can check out in my lecture 12 notes. There's just a bunch of problems that you have to figure out what technique to use. It's a very good way to do mathematics, by the way, to actually get just a random set of problems and try to do them, right, because, you know, on a test and things like that, you're goin to be given problems in a random order. They're not going to be, “Oh this is from chapter 1, so use chapter 1 techniques.” No, it's going to be, “Well this is a topic and you'll have to figure out what technique to use.” So it's a good way to practice and, again, if you need to see those or like to see those, problems and solutions are in Chapter 12, in my Chapter 12 notes, at the end of them.
So let's go to Chapter 1. So translating from mathematics to English. The first thing I'm gonna say is going to sound really obvious: make sure you know what a question is asking before answering it. I don't mean reading it I mean before answering it. Well why is that important? Well if you're trying to answer a question that you don't actually know what it says, it's going to be a lot harder than if you actually know what the question says. So it's really important to actually try to make sure that you really do understand what symbols are being used, what they mean, and what they are. I mean don't try to answer a question if you don't understand it, right? We're going to know you don't understand, and you're not going to be able to answer the problem. So stop, read the question, really make sure you understand what the symbols mean.
So some key words. We went through a couple of examples in class this week where we had $\forall$ and $\exists$ missing from the sentence, okay? So some key tip-offs to use a “for all” statement are things like “always”, “whenever”, “for any”, “none”, “no”. And keywords for meaning “there exists”, you're kind of looking “forsome”, “has a”, “there is” things like that, okay?
No multiple of $15$ plus any multiple $6$ equals $100$.
This is an example of a “for all” statement. Why? Because “no multiple”… so for every single multiple of $15$, and for every single of $6$, if I add them together and never get $100$. Written in math language it would look like:
$$\forall m,n \in \mathbb{Z},(15m+6n \neq 100)$$That's the way you should be reading it, and again, this takes practice. The second one I have here uses symbols:
$$n \in \mathbb{Z} \Rightarrow (\exists m \in \mathbb{Z},m \gt n)$$What is it really saying? Well if I start with any integer, then there's always a bigger integer than it. So what am I saying? Well there is no greatest integer; it's another way to say it, okay? Again, there's lots of ways to translate it, so don't just translate it line for line. You should try to get an understanding of what the thing is saying. If you do that, your life will be easier; it'll be better for you. It's easier to start a problem when you know what it's asking.
Contrapositive, okay. So we have two more proof techniques that we proved this week, and the first one is a proof by contrapositive. So what’s the idea behind this? Well if $H$ is the hypothesis and $C$ is the conclusion, then:
$$H \Rightarrow C \equiv \neg C \Rightarrow \neg H$$It's another way to prove things, so instead of starting with a hypothesis and proving the conclusion, you can start with the negation of the conclusion and prove the negation of the hypothesis.
What's a proof of this? Well a proof of this, you can actually do this symbolically. You can use a truth table as well:
$$H \Rightarrow C \equiv \neg H \lor C$$That is something that we sorted out in class. I'm going to flip the order around and that's still the same.
$$\begin{align*} H \Rightarrow C &\equiv \neg H \lor C\\\\ &\equiv C \lor \neg H \end{align*}$$Instead of $C$ I'm going write it as the negation of the negation of $C$. Two negations… two wrongs make a right.
$$\begin{align*} H \Rightarrow C &\equiv \neg H \lor C\\\\ &\equiv C \lor \neg H\\\\ &\equiv \neg(\neg C) \lor \neg H\\\\ \end{align*}$$And what's $\neg(\neg C) \lor \neg H$? Well if I look at this, this is ‘not’ the negation of $C$ implies the negation of $H$, well that's the same as $\neg C \Rightarrow \neg H$. So:
$$\begin{align*} H \Rightarrow C &\equiv \neg H \lor C\\\\ &\equiv C \lor \neg H\\\\ &\equiv \neg(\neg C) \lor \neg H\\\\ &\equiv \neg C \Rightarrow \neg H\\\\ \end{align*}$$The non-existent statements, these are usually really good times to use the contrapositive. $7 \nmid n$, that's a tough situation to start with, right, because all you know is that there is no integer such that $7$ times that integer is $n$. It's tough to deal with. It's a lot easier to deal with, well $14 \mid n$ well I know what that is. $\exists k \in \mathbb{Z}, 14k=n$, and then try to show that $7 \mid n$. So when you have these ‘not’ statements specifically in the conclusion but in the hypothesis and/or the conclusion, it might be a good idea to try to contrapositive. Just a general rule of thumb. Doesn't always work but at least it gives you something to try.
Let's see another example. So here's an example where it's maybe not so obvious to use but it will become obvious in a little bit:
Suppose $a,b \in \mathbb{Z}$ and $ab \in \mathbb{R} - \mathbb{Q}$. Show either $a \in \mathbb{R} - \mathbb{Q}$ or $b \in \mathbb{R} - \mathbb{Q}$.
So what does that mean? Well we're taking the real numbers, and we're removing the rational numbers. Well it's going to leave us with the irrational numbers. By the way, this is what I mean by reading the problem, right? If you don't understand what $\mathbb{R} - \mathbb{Q}$ is, then it's going to be a lot harder to answer this question, but if you do understand it's just a set of irrational numbers, it makes solving the problem a lot easier.
Here I'm showing that something is irrational. What does it mean to be irrational? If you define something with the words, “Well you're not rational,” that should tip off to you hey maybe I should use a contrapositive, or maybe I should use a proof by contradiction, which we'll see later. In this case, definitely a proof by contrapositive is the correct way to go. So we're going to proceed with a contrapositive, so what's the contrapositive of this? We're going to take the negation of the conclusion. Well the conclusion is, “$a$ is irrational $or$ $b$ is irrational.” So what's the negation of that? Ask yourself and say, “Okay well that's $a$ is rational $and$ $b$ is rational.” That's a lot easier to deal with. Dealing with $a$ is rational and $b$ is rational and proving something, thats a lot easier.
So we're going to start with that. What does that mean? Well then $\exists k,l,m,n \in \mathbb{Z}$ such that $a=\frac{k}{l}$ and $b=\frac{m}{n}$ with $l,n \neq 0$ Then what? Well okay what are we trying to show? Let’s making sure that we understand what we're trying to show. So we started with the negation of the conclusion. We're trying to show the negation of the hypothesis is true. Well what's the hypothesis? The hypothesis is: “$ab$ is irrational.” Don't worry about the $a, b \in \mathbb{R}$. That's sort of… that's above the statement, right? This is like a “$\forall\, a,b \in \mathbb{R}$, this implies this.” That's the way you should read this.
So here we want to show the negation the hypothesis which is: “$ab$ is rational”. Well what does it mean for $ab$ to be rational? Well I can write it as some integer divided by some other integer, and the bottom integer $\neq 0$. Well if $l$ and $n \neq 0$, the product is definitely not $0$. All of these are products of integers, so they’re still an integer, therefore $ab$ is going to be an integer over a non-zero integer, that’s a rational, and we’re done.
So there's an example of the use of contrapositive. When the conclusion contains the negation of an existence sort of thing. Again, just rules of thumb, when you use it, try it, and see if it works. If it works then you should use it. If it doesn't work, then try something else. Again, our toolbox of techniques are getting bigger, okay? So when you see a new problem, it's not going to be as obvious anymore what tool to use. In real life, you know it's very easy to know what screwdriver to use, or maybe not so obvious what wrench to use, maybe that's a better analogy here. Figuring out the size of the wrench to use can be tricky. You have to actually measure and try some things. But that's the idea now, okay? So we have a lot of tools. Now we have a wrench with lots of different, you know, socket pieces.
Types of implications. So we've seen these sort of implicitly throughout the course, but we're going to make a point right now to just go over the ways we can use $\land$ and $\lor$ and the hypothesis and the conclusion and how we prove these things.
$1)\, (A \land B) \Rightarrow C$
. We've seen this Divisibility of Integer Combinations, we've seen this in Bounds By Divisibility. Remember DIC was $a \mid b \land a \mid c \Rightarrow a \mid bx+cy$. Okay? So when we proved it, we assumed that $a \mid b$ and $a \mid c$, and when we use it, we must first prove that $a \mid b$ and $a \mid c$. So second one:
$2)\,A \Rightarrow (B \land C)$
So what does this mean? Well when we're trying to prove this, we're starting with $A$, we're assuming $A$ and we're trying to show that both $B$ and $C$ are true, and when we're using it we're proving $A$, and we get both $B$ and $C$ as being true for free.
So as an example,
$$\text{Let}\, S, T, U\,\text{be sets}.\,(S \cup T) \subseteq U \Rightarrow S \subseteq U \land T \subseteq U$$So again, this is sort of a “follow your nose” type of proof. You start with the hypothesis, well what are we trying to show? Let's start by showing $S \subseteq U$. Take an arbitrary element of $S$, it must in $S \cup T$, $S \cup T \subseteq U$, therefore every element of $S$ is in $U$, and we argue similarly for $T \subseteq U$. It’s the first time we saw the word “similarly” in class.
$3)\,(A \lor B) \Rightarrow C$
This is actually a little bit subtle, okay, which we'll see in a minute. So using this, you either start with $A$ being true, or $B$ being true, and then you get $C$ for granted.
Proving this, what do we need to do to prove this? Well let's take a look at this example. The example kind of helps us out here:
$$(x=1 \lor y=2) \Rightarrow x^2y+y-2x^2+4x-2xy=2$$How do we prove this? So we start by assuming the hypothesis is true, and the hypothesis is $x=1 \lor y=2$. Well what does it mean for an ‘or’ statement to be true? Well it means that at least one of these two things is true, but the question is which one? And the answer to that is you don't know. You don't know which one of these two facts is true, so you have to start with the one fact, so start with $x=1$ and prove that alone implies this equation is true. And then start with $y=2$, and use that alone to prove that this equation is true, okay? So you have to do… it's not just one thing. You have to do both things here, okay? You have to start with $x=1$, and prove the conclusion is true, then start with $y=2$ and prove the conclusion is true, okay?
The last thing that I want to talk about is part 4, which is elimination. This one's an important one as well.
$4)\,A \Rightarrow (B \lor C)\, \text{(Elimination)}$
So the way we can do this is we can eliminate one of the possibilities. Why can we do that? Well $A \Rightarrow (B \lor C)$. Well so we're going to take $A$ for granted, and if $B$ were true, then we'd be done, right, because then the conclusion is true and so the implication is true. So instead of trying to prove $B \lor C$, what we're going to do is we're going to take $\neg B$ as part of our hypothesis as well. And again why can we do that? If $B$ is true, we’re done the question. So you might as well assume that $B$ is false. If $B$ as false, then the negation of $B$ is true.
So start with $A \land \neg B$. If you want you can prove this by, again, logical equivalences things, like that, but I like that sort of case analysis in your head. You should be able to do that in your head by now.
So let's see an example:
$$\text{If}\,x^2-7x+12 \geq 0\,\text{then}\,x \leq 3 \lor x \geq 4$$Let me also note: you don't have to use elimination to solve this problem. It just makes life a little bit easier and cleaner if you do. What does elimination say? Well I'm going to take one of these two facts, I'm going to start with the first one just because, and take the negation of that as being true. So suppose that my hypothesis is true and that $x \geq 3$; the negation of one of my two statements in the conclusion. Then $0 \leq x^2-7x+12 =(x-3)(x-4)$. Since $x-3 \geq 0$, we know that $x-4 \geq 0$, since $(x-3)(x-4) \geq 0$, and hence $x \geq 4$. So that's the idea behind an elimination. You take the negation of one of the terms of the conclusion as true.
Contradiction, so proof by contradiction. This generalizes a proof by contrapositive. So if you never use contrapositive, you're not going to lose anything in terms of sanity. You should know what the word contrapositive means. There's lots of “C” words: contrapositive, contradiction, converse. Make sure that you have them all organized, but in terms of like actually leaving this course, if you always use contradiction instead of contrapositive, you're not losing any strength. You're not like missing a proof technique sort of thing. So something to keep in mind, but for the purposes of this course, you should know what both of these words mean.
That being said, what is a proof by contradiction? Well let $S$ be a statement, then $S \land \neg S$ is false. That sounds really obvious that one of $S$ or $\neg S$ is true and the other one is false. It seems really clear but it's something to keep in mind. How do we use this? How does this actually help us? A really obvious statement but it does help us a lot.
What do we do? Well we're going to assume the hypothesis is true, and we're going to assume towards a contradiction that the negation of the conclusion is also true, so we get the hypothesis and the negation of the conclusion. Now what are we going to do? Well we're going to break math. What does that mean? So to break math involves basically involves this: it involves finding a statement such that $S \land \neg S$ is true. What that statement is, it's not necessarily obvious when you start, but as you go through the proof you usually know when you’ve broken math in some way shape or form. Once you do that, you conclude the conclusion must be true, right? Only one of the negation or itself is true, so if the negation being true led to a contradiction, then the original conclusion must be true.
Example of a contradiction so use it in the same situations that you would consider using contrapositive. Here's an example:
Prove that $\sqrt{2}$ is irrational.
So contrapositive you need to use for implications, contradiction well…it's a little bit more general. It helps you out in situations like this where you don't have a visible implication. So here we go.
So prove that $\sqrt{2}$ is irrational. So proof: Assume towards a contradiction that $\sqrt{2}$ is rational, right? Being irrational is a difficult condition to deal with. Being rational is an easy condition to start manipulating. So we're going to assume towards a contradiction that $\sqrt{2}=\frac{a}{b}$, which is rational, and here though we're going to get a little bit more. We are going to also assume that $a,b \in \mathbb{N}$ instead of $a,b \in \mathbb{Z}$. Why can we do that? Stop and think about this and say, “Okay well $\sqrt{2}$ is positive. So if it's positive, then I know that $\frac{a}{b}$ is a positive number, so I might as well assume that both a and b are positive. If they were both negative… that's a possibility but then you can just cancel the negatives, and get something where both terms are positive, and we already know that $b \neq 0$ and we know that $a \neq 0$ because $\sqrt{2} \gt 0$.
Okay, we have all of those facts we are allowed to assume, in this case, that $a,b \in \mathbb{N}$. You should write this down in your proof. I'm not going to because I want to fit on this slide.
Assume further that $a$ and $b$ share no common factor, right? If they did share a common factor, then you could simplify the fraction before declaring what $a$ and $b$ were, okay? So we're also going to do that. Then by some arithmetic we have:
$$\begin{align*} \sqrt{2}&=\frac{a}{b}\\\\ \sqrt{2}b&=a\\\\ 2b^2&=a^2 \end{align*}$$ What does that mean? Well it means that $a^2$ must be even, and hence $a$ is even, okay? So if $a^2$ is even, then we know that $a$ is even, we saw that in class this week as well. You can check that out in lecture 10.So write $a=2k$ equals $2k$ for some $k \in \mathbb{Z}$, then substitute that into $a^2=2b^2$. What do we get? So we get:
$$2b^2=a^2=(2k)^2=4k^2$$Cancelling a $2$ shows that $b^2=2k^2$ and then, once again, $b^2$ is even, hence $b$ is even. Well $a$ is even and $b$ is even, so that means that they share a common factor, namely $2$, and that's a contradiction. Okay?
So what did we contradict? Well we said that $a$ and $b$ had no common factor, but here we've shown that $a$ and $b$ have a common factor. So my $S=$ “$a$ and $b$ share no common factor.” Well I've shown that $S$ and $\neg S$ were both true. So $S \land \neg S$ is true, well that's a contradiction. That doesn't make sense. So because I broke math, because I've reached a contradiction, I conclude that the thing that I assumed was false. I assumed that $\sqrt{2}$ was rational so therefore $\sqrt{2}$ is irrational. Should you include a concluding sentence, “therefore $\sqrt{2}$ is irrational”? It's good form, I didn't here. you should probably do it. Do what I say not what I do.
Uniqueness. To prove uniqueness, what do we do? So we have two options to prove uniqueness: we assume that there are two elements $x$ and $y$ inside some set $S$ such that these statements $P(x)$ and $P(y)$ are true, and then show that $x$ equals $y$, that's the one thing we can do, and the second thing we can do is we can argue by assuming that there are two elements $x$ and $y$ inside $S$ that are distinct such that $P(x)$ and $P(y)$ are true, and then derive a contradiction somehow. So start with two distinct things, and break math in some way, shape, or form.
So to prove uniqueness and existence, don't forget that you actually have to show that there is one such $x$, so there are two elements to uniqueness and existence. Uniqueness is just showing that if an element exists it must be the only element, and existence means finding such an element. Remember that we said that we used another symbol here, $\exists!$ That means that “there exists a unique…”, okay?
How about an example of uniqueness? So here's our question:
Suppose that $x \in \mathbb{R} -\mathbb{Z}$ and $m \in \mathbb{Z}$ such that $x \lt m \lt x+1$. Show that $m$ is unique.
So again, this is tough to do unless you actually read and understand what the sentence is. “Suppose $x$ is a real number that's not an integer,” so it’s what we call a non integral real number, that’s one way to word it, and $m \in \mathbb{Z}$ such that $x \lt m \lt x+1$. Show that $m$ is unique. What does this really mean? Let's take an example say $x=3.3$ So if $x=3.3$, then $x+1=4.3$ and $m \in \mathbb{Z}$ such that $3.3 \lt m \lt 4.3$ Okay, well it's probably the integer $4$ since I don't think there's any other ones… well we're showing that m is unique, okay, so that's kind of the idea here. You're showing that there was only one integer between some decimal number and the decimal number +1.
It's important that you don't include the integers for your $x$ because if you included let's say $0$, then $0 \lt m \lt 1$, well there is no integer between $0$ and $1$. So we need $x$ to be a non-integral real number.
So how does the proof of this go? Well what are we going to do? We're going to assume that $\exists m,n \in \mathbb{Z}$ such that $x \lt m \lt x+1$ and $x \lt n \lt x+1$. And now what are we going to do? Well let's look… so now comes the sort of the clever part of this proof, and when you look at $m$ and $n$, well the bounds are identical. So because the bounds are identical, it seems to suggest that if we look at the difference then we're going to learn some information here.
So let's look at the difference $m-n$. The value, $m-n$, is largest when $m$ is largest and $n$ is smallest, so when is $m$ largest? Well when it's as close as possible to $x+1$, and when is $n$ the smallest? Well it's the smallest when it's as possible to $x$. Well what's that difference? That difference is bounded above by 1, right? If $m=x+1$ and $n=x$, well that difference, that length, is $1$. So $m-n \lt 1$
For this to be minimal, you flip the roles of $m$ and $n$, so take $n$ largest and $m$ smallest. Well we're going to see that $-1 \lt m-n$ and these are strict inequalities. So combining these two facts what do we get? $-1 \lt m-n \lt 1$. And $m-n \in \mathbb{Z}$. There's not too many integers between $-1$ and $1$. In fact we know all of them it's $0$. But $m-n$ is an integer in this range, so $m-n$ must be $0$, and that is $m=n$. That completes the proof.
So it's just another way to… again, uniqueness so how do we do this? Again, start with two values, and either assume they're distinct and reach a contradiction or take the two values and show that they must be equal. In this case, we took two values and show that they were equal.
Uniqueness, we saw a couple of examples, so a couple of areas where we could use uniqueness. One of them was with injections and surjections. So I'm going to talk a little bit about function notation here.
So let $S$ and $T$ be sets, a function $f$ from $S$ to $T$ and we use this notation, $\,f:S \rightarrow T$. So what does this notation mean? A lot of things have sort of changed from here and from your previous, let's say calculus courses or high school courses. Functions have a domain and a co-domain given to you. Here we call $S$ the domain, and here we call $T$ the codomain. Some of you have heard the word “range”. What is range? Well range is the set of all values that the function takes. So, for example, I could define a function $f:\mathbb{R} \rightarrow \mathbb{R}$ defined by $x \mapsto x^2$. Well the range of this function is only all non-negative numbers, since $x^2 \geq 0$. So the range is all non-negative numbers, but the co-domain is all real numbers, okay? So a function has a domain and a co-domain given to it. So the question: “find the domain of the function,” it should just be well it’s $S$, right here obviously. That question really should be very obvious, okay?
Now you could ask, “Can I extend the domain of $f$ to make sense in other places?” That makes sense too, but a function should have a domain given to you, and a co-domain given to you.
This notation $x \mapsto f(x)$, what does it mean? Well it means that I'm going to take $x$ and map it to something, so that value we call $f(x)$. So in the past, you used to see, “define a function $f(x)=x^2$” something like that, right? Here, I'm going to define it using the more general notation and this is used in many upper-year courses, so I wanted to introduce it now because I feel like it's a really good time to get your head around functions.
So a function $f: S \rightarrow T$ defined by $x \mapsto f(x)$ is said to be injective, sometimes we use the words, $1:1$, if and only if:
$$\forall x,y \in S,\,f(x)=f(y) \Rightarrow x=y$$What does this really mean? Again, so a bunch of symbols. I know how to prove this, right, I start with $f(x)=f(y)$ and show that $x=y$ true. What is this actually telling you? If I take an element from $T$ that is mapped to from something from $S$, so something that is actually mapped to, it must only be mapped to in one way, okay?
So the way to think about this is like $S$ is a group of boys and $T$ is a group of girls, okay? So if a girl has a dance partner, they only have one dance partner. That's kind of what this is saying, right?
Now let’s look at it the other way surjective, or onto, if and only if:
$$\forall y \in T, \exists x \in S \,\text{such that}\,f(x)=y$$So let's go back to that party example. So $S$ is the set of boys, $T$ is the set of girls. What is this saying? This is saying that every girl has a dance partner. So maybe a girl has two dance partners, you know lucky girl, that's fine, but it means that every girl has a partner, that's what it means to be onto, and $1:1$ means that if a girl does have a partner, it must be a unique partner. That's the idea behind the injections and surjections. Again, there's lots of examples in the notes. I'm not going to do them here. I'll say, go to the notes. Go to the Math 135 Resources Page. Check out some typed examples. Check out some of the examples for my notes.
One more example of uniqueness was the division algorithm. What is the division algorithm? It’s basically grade school division. You do your long division, okay? So if I wanted to divide $7$ by $51$, I would write my $7$ goes into $51$ how many times? Well $7$ goes into $5$, $0$ times, $7$ goes into $51$, $7$ times, what's my remainder? $2$. So $51=7(7)+2$.
Another example: $35$ divided by $6$. Well how many times does $6$ go into $35$? It goes in $5$ times. $6 \times 5=30$ the remainder is $5$. So $35=6(5)+5$. If you wanted to do it with a negative value for $a$, what would we do? So negative value on the left, so I do it with the positive version first, take the negation of everything:
$$-35=6(-5)-5$$Only one of these terms need to be negative if I multiply everything by $-1$, and I'm going to subtract 5. But now I'm going to insist that my remainder be positive, so what do I get for my remainder to be positive? I’m going to add an extra value 6, and that's going to give me:
$$-35=6(-5)-6+6-5=6(-6)+1$$So that's the way to do it, this is the way I think about it when I have negative values for $a$ in the division algorithm, okay? I go through this two-step process.
The division algorithm, so what does the division algorithm say?
Let $a \in \mathbb{Z}$ and $b \in \mathbb{N}$ then $\exists !\, q,r \in \mathbb{Z}$ such that $a=bq+r$ where $0 \leq r \lt b$
$q$ and $r$ don't technically have to be unique until we envoke the condition that $0 \leq r \lt b$. So keep in mind somebody asked me, “Well why can't $r=b$?” And I said, “Well if $r=b$, then just take off another copy of $b$, put it into $q$ and make your remainder $0$.” Okay? It's like basically like writing, well $6=0+6$. No you should have written it as $6=6(1)+0$. That's the difference there.
The proof, I didn't do it in my class. Some classes probably did do it. I recommend reading the proof, I really do. It's a good example of uniqueness. Existence is tricky, and actually this is this thing called the “Well Ordering Principle”. It's a clever argument, you can check that out on Wikipedia, but for now the proof in the notes…it's there and you should read it. It's a good example of uniqueness, and one more example.
The last thing I want to talk about is summation and product notation. So again your class might not have done this. So on Friday, I gave my class a bunch of sample problems to go through and to solve using all the techniques up to this point. By Friday, we will actually been 12 lectures - well 11 lectures completed. So you have a lot of proof techniques, and now when you actually read a problem, it's tough to know where to start the problem. So that was part of what I did on Friday, and the other part of what I did was summation product notation. Now why did I do this? So next week, we're heading into something called mathematical induction, and this notation will appear everywhere. So my theory is that you should see this. Spend some time with it over the weekend, actually make sure you understand it because again if you're going to get problems that involve this notation and you have to think about what the notation means, it's going to be harder to solve the problem. So spend some time with this notation this week and really make sure you understand what it means so that when you see problems with it, you know what to do. You know what it means you don't have to think about what these words mean, okay? It's really important.
So okay, summation and product notation. Well let $\{a_1,..., a_n\}$ be a sequence of real numbers. In this case, $n$ real numbers. We're going to write:
$$\sum_{i=1}^n a_i :=a_1+a_2+...+ a_n$$We'll see some examples in the next page. But basically what does this mean? It means add all of the elements $a_i$ from $i=1$ to $n$. So if you understand programming language stuff, this is similar to a ‘for loop’, something like this. A ‘for loop’ of a sum. We call $i$ the index variable. We say that $1$ is the starting number and $n$ is the upper bound or the finishing number, the final index, all of these words, okay?
We can also write summation notation as follows. If $S$ is a set:
$$\sum_{x \in S} x$$We can write $x \in S$ to mean the sum of the elements of $S$. Of course this has to make sense, so $x$ has to have some addition operation on it. So let's say $S$ is the set of integers, or real numbers, something like this. If $S$ is the set of all hockey players on a hockey team, then clearly this doesn't make any sense, so it has to make sense to actually do this.
Similarly, we define product notation:
$$\prod_{i=1}^n a_i :=a_1a_2...a_n$$So this is a big product. So here I should note also I've used $:=$ for the first time which means “defined to be”, okay? So I’m defining this notation to be this product. I'm defining this notation to mean this sum. I'm defining this product notation over $x \in S$vis the product of elements in $S$, okay? This product notation, $\prod$ is a capital letter pi by the way. \prod in LaTex. \sum is the big summation, $\sum$. Capital sigma that's what it is.
We also make a couple of following conventions when $j \gt k$ are integers:
$$\sum_{i=j}^k a_i = \sum_{x \in \emptyset}=0 \qquad \text{and} \qquad \prod_{i=j}^k a_i=\prod_{x \in \emptyset}=1$$So in words, if the starting index is bigger than the final index, we're going to call the sum the “empty sum”. We're also going to define the sum over the empty set to just be $0$. That's just what we're defining it as, it's just a definition it makes life easier, it works in a lot of nice situations. Take it as it is, okay?
We're also going to define the product if the starting index is bigger than the final index to be $1$. And again this is the same as the product over the empty set. Just notation, just to make life easier, okay, the empty product is $1$, the empty sum is $0$. Just makes life easier. You'll see if you actually read papers and stuff that use this stuff. It just usually works out in this case.
Some examples, so we're going to finish off with a couple examples. Make sure we understand the notation.
What does that mean? Well how do we do this? We start off with $i=1$, we plug it in, we square it. That's the first term. Increment your counter to $2$. $2 \leq 4$, plug in $2$. $2^2$. Increment the counter to $3$. $3 \leq 4$, plug in $3$, $3^2$. Increment the counter you get to $4$. $4 \leq 4$, plug in $4$, $4^2$ Increment the counter we get to $5$. $5 \gt 4$, we stop. Those are all the terms. Then we can just add them up and we get $30$.
$$\sum_{i=1}^4 i^2=(1)^2+(2)^2+(3)^2+(4)^2=1+4+9+16=30$$Similar with product notation, right, same sort of idea.
$$\prod_{i=1}^4 i^2$$Plug in $i=1$, we're going to get $i^2$, so $1^2$, and we're going to multiply that by the next term, right, so instead of $1$, we plug in $2$. So $1$ goes to $2$, $2$ we plug in, $2^2$. Increment the counter to $3$, plug in $3$, $3^2$. Write that down and get us a product. Increment the counter to $4$. $4 \leq 4$, plug it $4$, $4^2$. Increment the counter we get to $5$. $5 \gt 4$, we stop. Take the product of all these numbers:
$$\prod_{i=1}^4 i^2=(1)^2(2)^2(3)^2(4)^2=(1)(4)(9)(16)=576$$Another example, you won't see this too often:
$$\sum_{i=1}^{3.5} i$$You go $1, 2, 3,$ and $4 \gt 3.5$ so you're done.
$$\sum_{i=1}^{3.5} i=1+2+3=6$$Usually you write this with integers, you can do it with decimal numbers too. I've actually never really seen this, but this is one way to define it.
Here's more of a convoluted example:
$$\text{For}\, k \in \mathbb{N}\, \text{fixed}, \sum_{i=k}^{2k} \frac{1}{i}$$Well again, it's the same idea. Start with $k$, plug it in, then increment the counter to $k+1$. If $k+1 \lt 2k$, we can write it, and you keep going. $k+1,k+2,k+3$, we go all the way up to… what's the last term? $\frac{1}{2k}.$
$$\sum_{i=k}^{2k} \frac{1}{i}=\frac{1}{k}+\frac{1}{k+1}+...+\frac{1}{2k}$$Now something to think about, right? If we're going to keep doing this, $k,k+1,k+2,k+3$, what's eventually going to happen is we're going to write $k$ in two different ways. We're going to write it as $k$ plus some number, $k+1,000,000$ who knows. It depends on what $k$ actually is. So let's say $k+j$, and we're going to also write it as $2k$, right? Eventually $k+j=2k$ for some $j$. So don't let that confuse you here. Again it's just you start from the index $\frac{1}{k}$, and you just increment all the way up to $\frac{1}{2k}$. That's all this means. There are other convoluted ways to write it, but this is the main idea, okay?
In the first few examples, it was easy because we knew what the index was. If you don't know what the index is, you can use dots. The summation notation is supposed to take the place of these dots, and makes it look a little cleaner and nicer, but if you need to when you're learning this notation, feel free to write down the dots if it helps you out.
So that's all I have to say for this video. Again hopefully this helped you, gave you some ideas, clarified things from class. If not again, as always, send me an email, send me a post on Piazza or wherever. I'm usually around I'll hopefully answer your questions. Really I just hope this helped. I'm trying to make this a good learning tool, so let me know. Any feedback is great, and thank you very much and good luck.