Hello everyone. Welcome to Week 4 of Carmen's Core Concepts. My name is Carmen Bruni, and in these videos, we talk about the week's worth of materials in Math 135, but we're going to go through this very quickly, so again, this isn't meant to be a substitute for not going to lectures, or not doing homework, or not actually trying problems, right? These are just meant to supplement the course and hopefully help you if you missed something during the week, or need a clarification on something.
So let's talk about what we're going to do this week. Again, the idea behind this slide is meant to be sort of a timestamp thing if you want to try to find this, you can go to this approximate minute stamp. What are we going to talk about in this video? We're going to talk about the Principle Mathematical Induction, that was the main topic of the week. We'll see an example and we'll highlight the base case, the inductive hypothesis, and the inductive step. We're going to talk about when induction isn't enough, so a situation where the usual or the typical induction statement’s not going to work, and that's where we would like to use something called strong induction, which will help us out so we'll talk with that in slide 7. I'm going suppress from this video an example of strong induction, You can go on the Math 135 Resources Page and check out an example of strong induction there.
Then we're going to talk about the Fibonacci sequence, or just remind ourselves what it is, and that's all we'll say about that, and then the last four bullets, so this is where my course might differ from your course substantially. I decided to do the Fundamental Theorem of Arithmetic as the last lecture of the induction week. It turns out that we can't actually do it. We actually need something called Euclid's Lemma that we don't have yet, but we will prove that next week, but assuming that we can actually do the Fundamental Theorem of Arithmetic, particularly see the proof. I think it's one of the most difficult proofs in this course to do formally, so in class I did it formally. Here I'm going to… well okay I should say in class in January 2016, I did it formally. But in this video, I’m going to do it informally. I'm going to do an existence proof formally, and we're going to do an informal uniqueness proof just to kind of get the idea down. The formal proof kind of takes away from what's really going on, and I think the informal proof is good to see once. So this is the outline for this week.
Principle of Mathematical Induction, this is how we started our week. So this is an axiom of mathematics.
Principle of Mathematical Induction (POMI):
$\text{If a sequence of statements}\,P(1),P(2),...\text{satisfy}$
$$\begin{align*} &1)\, P(1)\, \text{is true}\\\\ &2)\, \text{For any}\, k \in \mathbb{N}, \text{if}\, P(k)\, \text{is true then}\, P(k+1) \, \text{is true} \end{align*}$$$\text{then}\,P(n)\,\text{is true for all}\, n \in \mathbb{N}$
The analogy to think about here is like a domino analogy, okay? So here I don't have dominoes I have little jewel cases that I'm going to stack up, and so the idea is if you have infinitely many jewel cases, so I only have three here but you can imagine that this goes on forever, and the idea is that I want to knock them all down. So if $P(1)$ is true, I can knock down the first one, and for any $k \in \mathbb{N}$, if the $kth$ one gets knocked down, then the $k+1st$ one gets knocked down, then all the dominoes will get knocked down, right? That's the idea here, right? So if I push the first one down, then it will knock the second, and the third, and the fourth and so on, and that's how the Principle Mathematical Induction works. So the idea is if $P(1)$ is true:
$$P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow P(4) \Rightarrow ... \Rightarrow P(n)$$As long as I can prove $P(1)$, then all of them will fall.
So we gave a couple of examples of bad induction proofs in class. Maybe I'll just mention what the sort of idea is here. So here's an example, you can imagine if I had the first two dominoes that were close together, and the third domino being more than one domino length away from the second one. This would be an example where $P(1)$ and $P(2)$ are true, but $P(2) \nRightarrow P(3)$. If I knock down $P(2)$, I don't knock down $P(3)$. It's too far away. So the mathematical analogy is just that they don't imply each other.
So that was similar to the horse one where we saw that $P(1)$ didn't imply $P(2)$. Again if you're looking for that horse example, it will be in lecture 16 on the Math 135 Resources Page.
Okay so that's the domino analogy. Again so if I can show that the $kth$ is true implies that the $k+1st$ is true, and $k$ is an arbitrary natural number, then I've shown that all of them are true provided of course I can show that the first one is true.
Let's see an example. So again the statement’s sort of one thing, and actually proving things with Mathematical Induction feels like a different sort of set of skills. I usually find that students have trouble with the statement, but have no problems actually proving things with Mathematical Induction. So let's see an example:
$\text{Prove that}$
$$\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$$$\forall n \in \mathbb{N}$
So again what is this sum on the left mean? We're trying to prove this for all natural numbers $n$, so we have infinitely many statements. Now what does this sum mean? Well the sum is the sum of all squared numbers from $1$ to $n$. So $(1)^2+(2)^2+(3)^2+(4)^2$ so $1+4+9+16+...$and so on and so forth, okay? All the way up to $n^2$. We're trying to show that sum is equal to this nice closed form expression, so $\frac{n(n+1)(2n+1)}{6}$ is called a closed form expression. We saw one example in my class, of how to actually determine the closed form expression. It's one part, you know, guessing and one part perseverance, you know. You just have to kind of try some numbers and hopefully see the pattern, if you want to try to figure out the closed form without being given it.
How’s the proof… So how is the proof of this going to work? We’re going to let $P(n)$ be the statement: $\sum_{i=1}^n i^2 =\frac{n(n+1)(2n+1)}{6}$, and that this holds. So we're going prove that $P(n)$ is true for all natural numbers by the Principle Mathematical Induction.
So step one is always the base case, okay? So when $n=1$ this is the statement that we'd like to prove:
$$\sum_{i=1}^1 i^2=\frac{(1)((1)+1)(2(1)+1)}{6}$$Why does this hold, in this case? Well the expression on the right can be simplified to:
$$\frac{(1)((1)+1)(2(1)+1)}{6}=\frac{(1)(2)(3)}{6}=1$$This sum is just the sum from $1$ up to $1$ of $i^2$ so $1^2$ and that's just $1$. So in the base case, it's very simple. Usually base cases are easy. If they're not, then you're probably missing something. So that's the base case. So we've proved that $P(1)$ is true, right, that was the first part of Mathematical Induction.
Now the second part is: “If $P(k)$ is true, then $P(k+1)$ is true.” So how do we break that down? Well we have our hypothesis which is: “$P(k)$ is true for some $k \in \mathbb{N}$” and we'd like to show that $P(k+1)$ is true given that we know that $P(k)$ is true. So here we have our induction hypothesis then.
We're going to assume that $P(k)$ is true, the key words here are “for some $k \in \mathbb{N}$". So we don't know what $k$ is, but we know it's a natural number and it’s an arbitrary natural number. Maybe it's a million, maybe it's $10$ million, maybe it's a gagillion, whatever it is it's some natural number, okay?
What does this mean? So what does $P(k)$ being true mean? Well it means that the following statement holds:
$$\sum_{i=1}^k i^2=\frac{k(k+1)(2k+1)}{6}$$That's our inductive hypothesis.
Now getting to the inductive step, or the inductive conclusion, it's involved okay, so the next slide is going to be a little bit involved. There's just no way around it. Otherwise I have to break it up, and I'd rather put it all on one page. So this is something that I want you to remember. Hopefully write down on a piece of paper or something, pause the video and do that because we're going to use it on the next slide.
The inductive step, so what are we doing in the inductive step? Well we'd like to show that:
$$\sum_{i=1}^{k+1} i^2=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$$Now how do we do this? Well what's the technique for these sums? So it depends on what kind of sum you have. Here we have a very simple sum where only the top index is changing. So usually what will happen in this case is you'll just pluck off the last term, and you'll be left with a $k$ term:
$$\sum_{i=1}^{k+1} i^2 = \sum_{i+1}^k i^2 + (k+1)^2$$The sum, $\sum_{i+1}^k i^2$, that's reminiscent of the inductive hypothesis. And that's the thing that we're going to substitute here, okay? That's the main idea here. So we're going to take the sum, break off the last term, go from $1$ to $k$ of $i^2$ and we're going to get the above equality.
Something to keep in mind, so sometimes it doesn't work out this nice. They sometimes both indices depend on $k$, it really does depend on the question, and the summation. So you have to pay attention as to where the variable is in your question, where the indexing variable is. There’s a difference between the variable $n$ and the variable $i$ here. Make sure you understand that difference. If not I suggest going back to CCC Week 3 video. We talked about that in there.
Okay assuming that all that is good, we have now our sum from $1$ to $k$ and we took off the $(k+1)^2$ term, okay? We now have:
$$\begin{align*} \sum_{i=1}^{k+1} i^2 &= \sum_{i+1}^k i^2 + (k+1)^2\\\\ &\overset{IH}{=} \frac{k(k+1)(2k+1)}{6} +(k+1)^2 \end{align*}$$Now we're using the inductive hypothesis that's what the “IH” over the equal sign means. You should state when you're using the inductive hypothesis, that's very important. It's very important to let the reader know that you know what you're doing. You're not just sort of symbol mashing. You can also write down words “by the induction hypothesis”, “by the inductive hypothesis”, that's fine as well. Here I'm just going to put it as "IH" because clearly I'm running out of room on this slide. So the sum of squares from $1$ to $k$ is given by the above expression, that was the inductive hypothesis, and then plus $(k+1)^2$.
When you get to this point, you have options. Option 1 is to expand everything. When you can avoid it, it's usually good to try to avoid it. In this case, we can avoid it. We can actually factor. We have the $k+1$ term that we can pull out, and this makes sense to do because we also need a $k+1$ in our final answer, so pulling out this $k+1$ factor should help us out a lot. So pulling that out we have this left:
$$\begin{align*} \sum_{i=1}^{k+1} i^2 &= \sum_{i+1}^k i^2 + (k+1)^2\\\\ &\overset{IH}{=} \frac{k(k+1)(2k+1)}{6} +(k+1)^2\\\\ &=(k+1)\left(\frac{k(2k+1)}{6} +k+1 \right) \end{align*}$$Find a common denominator, add the terms, and now in the numerator, we have $2k^2+7k+6$. Factor. My favorite “F” word:
$$\begin{align*} \sum_{i=1}^{k+1} i^2 &= \sum_{i+1}^k i^2 + (k+1)^2\\\\ &\overset{IH}{=} \frac{k(k+1)(2k+1)}{6} +(k+1)^2\\\\ &=(k+1)\left(\frac{k(2k+1)}{6} +k+1\right)\\\\ &=(k+1)\left(\frac{2k^2+k}{6}+\frac{6k+6}{6}\right)\\\\ &=(k+1)\left(\frac{2k^2+7k+6}{6}\right)\\\\ &=\frac{(k+1)(k+2)(2k+3)}{6} \end{align*}$$And that's it. So once we factored it, we have $k+1,k+2,2k+3$ that's what's left. Hence, the sum of squares is equal to what we expect. Why is that true? Well that's true because of the Principle of Mathematical Induction, right? We showed that $P(1)$ is true and that $P(k) \Rightarrow P(k+1)$. Hence this is true $\forall n \in \mathbb{N}$.
And that's induction in three or four slides. That's the main idea. Again we saw this all week. We saw lots of examples, we saw examples using summations, I did one using a chocolate bar, we've done all kinds of examples. Sequences, we'll get to sequences in a minute, but I mean this is a concept that you really should understand, and really make sure that you you get solidly down. It takes a while to write up and these arguments do take a little bit of time, but once you get the hang of it, they're very quick. And I like to call these “follow your nose” type of things, right? You know that with the inductive step, you need to get back to the inductive hypothesis, so make that appear. Do a little bit of symbol rearranging, expand or factor is usually the trick and get the result you want.
When induction isn't enough. So sometimes we have a problem where the statement feels like it should be proved by induction, just simple ordinary induction on the statement itself, but sometimes it's maybe not so obvious how to do this. So it turns out…so maybe a little bit of a spoiler here, it turns out that weak induction, or the Principle of Mathematical Induction and strong induction, which we'll see on the next slide, it turns out they are equivalent. You can actually prove that they imply each other. This proof is not easy - well one direction is easy the other direction is actually a little bit tricky to word, but it does emphasize that all things could be proved with weak induction, but just the statement that you have to prove is actually trickier.
In this case, anyways all that meta aside, let's look at this example:
Let $\{x_n\}$ be a sequence defined by $x_1=4,x_2=68$ and
$$x_m=2x_{m-1}+15x_{m-2} \qquad \text{for all}\, m \geq 3$$Prove that $x_n=2(-3)^n+10 \cdot 5^{n-1}$ for $n \geq 1$
So this is what you call a recursive definition, or recursive statement, all of these things. Recursion statement, all of these things mean the same thing. $x_m$ is defined in terms of previous terms. So if I wanted to determine $x_3$, I would plug in $3$ into the formula:
$$x_3=2x_2+15x_1=2(68)+15(4)=128$$What are we going to prove? We're going to prove here that $x_n=2(-3)^n+10 \cdot 5^{n-1}$ And we're going to try to do this by induction, okay?
The base case for $n=1$, we plug it in and we see that it works. $x_1=4$ and
$$2(-3)^1+10 \cdot 5^{1-1}=-6+10=4=x_1$$The inductive hypothesis, we're going to assume that $x_k=2(-3)^k+10 \cdot 5^{k-1}$ and we're going to assume this is true for some $k \in \mathbb{N}$.
Now for $k+1$, well what do we do? Well okay we have $x_{k+1}$, and now we have a couple of problems here. We either have that $k+1=2$, right, because again all we know is that $k \in \mathbb{N}$ so $k+1 \geq 2$, if $k+1=2$, then we'd have to do another case. So we might need multiple base cases, it's something to think about.
But let's just assume that we could prove the $k+1=2$ case. So let's assume that we can prove that $P(2)$ is true as well. So take that for granted so let’s assume that $k+1 \geq 3$. We can use the recursion statement, the recursive relation between $x_{k+1}$ and its previous terms. So let's just suppose that this is true, and even if this was true we can substitute and get:
$$x_{k+1}=2x_k+15x_{k-1}$$The problem is we still have this $x_{k-1}$ term. And what's happening is that our induction hypothesis, or inductive hypothesis is too weak. It's not strong enough to give us the result that we want. So in order to do this, we need…well use one or two ways. One, we can reword the statement that we're trying to prove, that's harder, or the easier way is to use something called strong induction. So that's what we're going to see now.
The Principle of Strong Induction. Again, this is an axiom. As I said this is equivalent to the Principle of Mathematical Induction. It's not so easy to prove, but you can do so. It's also equivalent to the Well Ordering Principle which we saw last week in last week's video. That's an axiom I like a lot, I think it’s pretty interesting and has a lot of cool consequences. Same as induction, but it's worded in a very easy way.
Principle of Strong Induction (POSI)
$\text{If a sequence of statements}\,P(1), P(2),...\text{satisfy}$
$$\begin{align*} &1) P(1) \land P(2)\, \land ... \land \,P(b)\, \text{are true for some}\, b \in \mathbb {N}\\\\ &2) P(1) \land P(2)\, \land ... \land \,P(k)\, \text{are true implies that}\, P(k+1)\, \text{is true for all}\, k\in \mathbb{N} \,(k \geq b) \end{align*}$$$\text{then}\, P(n)\, \text{is true for all}\,n \in \mathbb{N}$
So what is this really saying? What this is saying is, instead of assuming that just $P(k)$ is true and proving that $P(k+1)$ is true, we're going to assume that all the statements from $P(1)$ to $P(k)$ are true.
So if we think about this in the domino analogy, it's no longer that we're just assuming that the $kth$ domino falls implies that the $k+1st$ domino falls, we're assuming that the first $k$ dominoes have already fallen and that implies that the $k+1st$ domino has fallen. That's the idea behind the Principle of Strong Induction.
Now it turns out because you're proving multiple base cases possibly, you can also take $k \geq b$ here. So again $b$ is just some natural number. Again so in the Principal of Mathematical Induction, you always have $b=1$, we only prove the first case and then the second implication step, we have $P(k) \Rightarrow P(k+1)$. Here we have $P(1), P(2)$ all the way up to $P(k)$ implies $P(k+1).$ Now typically you don't use all of the cases. Sometimes it helps to know they're all true. Sometimes you only need a couple of previous steps. Either way is fine. But that's the idea behind the Principle of Strong Induction.
Now if you want to see an example, I'm not going to do an example here because they do take a decent amount of time and they are quite convoluted, but I do have other videos on the Math 135 Resources Page where you can check out if you want to see an example of strong induction. I also explain how to know when to use strong induction, and when to use weak induction. Pretty much I always start the proof by induction, and if I get stuck or if I need multiple base cases or if I need to go back a couple of steps before, instead of just $P(k)$ I need $P(k-1)$ and $P(k-2)$ being true, something like that, then I'll go back and change my proof to be strong induction. So I usually just leave a couple of blanks just in case I need to prove something with strong induction. Okay so that's the Principle of Strong Induction.
Maybe one last little topic here that fits in nicely, the Fibonacci sequence. This is a beautiful sequence in mathematics, and we define it as follows:
$\text{Let}\, f_1=1\, \text{and}\, f_2=1\, \text{and}$
$$f_m=f_{m-1}+f_{m-2}$$$\text{for all}\, m \geq 3.\, \text{This defines the sequence}$
$$1,1,2,3,5,8,13,21,34,55,89,...$$It's a cool sequence, it appears in lots of applications. One of my favorite things to tell students is to go online and look up a YouTube video by a band called Tool and the song is called Lateralus and it uses the Fibonacci sequence in a really cool way. I think it's a really neat song, and it's also a good song in its own right. So check that out if you're interested in music or if you want to see some cool applications of the Fibonacci sequence. There are lots, that's just one of my favorites that I'll mention to you.
Again this is one of these things you should just know. You should know the Fibonacci sequence. Every term after the first two, which are both $1$, is defined as just the sum of the previous two terms. You should know the sequence. We’ve seen a couple of proofs in class of induction statements that use the Fibonacci sequence. Again, it's just a beautiful topic. It's a beautiful sequence.
The last thing I want to talk about this week is the Fundamental Theorem of Arithmetic. So I always joke with students and I say you know, “If something is called the Fundamental Theorem of something, you know insert subject name here, you should probably know it. You should probably know it inside out, you should know it frontwards, backwards, in different languages, you should just know the theorem, okay?” It's probably important.
So what do we need to do this? So we want to prove the Fundamental Theorem of Arithmetic, which we'll get to in the next slide, but before we do that we’re going to need a couple of tools that we don't have yet, so we're going to take these for granted and in the following week, we'll talk about the proofs of these things.
The first thing that we’ll need is Euclid's Lemma, and in our notes we call it Primes and Divisibility, for now. I'm hoping just to get this changed to Euclid's Lemma. This is the name of the theorem in general, but in this course we've called it Primes and Divisibility and we use the acronym, PAD.
$\text{Let}\, a,b \in \mathbb{Z}\, \text{and let} \, p \, \text{be a prime number. If}\, p \mid ab \, \text{then}\, p \mid a\, \text{or} \, p \mid b$
This seems really obvious. If $7 \mid (14)(20)$, then $7 \mid 14$ or $7 \mid 20$. It feels really obvious, but it's actually not completely trivial to prove. There's actually a little bit of thought that has to go into this proof. But we'll see that next week. This actually will follow quite nicely from our work with greatest common divisor, which is where we're going. Our goal is to prove this basically next week.
A corollary from this, and this is actually in the January 2016 term we actually will get you to prove this; this Generalized Euclid’s Lemma:
$\text{Let}\, a_1,a_2,...,a_n \in \mathbb{Z}\, \text{and let}\, \text{be a prime number. If}\, p \mid a_1a_2...a_n\, \text{then}\, p \mid a_i \\\\ \text{for some}\,1 \leq i \leq n.$
$p$ could divide more than one term, but it must divide at least one, okay? It turns out this Generalized Euclid’s Lemma is really what we're going to need. This follows quite nicely from Euclid's Lemma and I won't say anything more other than this because at least in one class we’ll prove it, but that's it.
So with these tools, again, so the Generalized Euclid’s Lemma just keep in your mind, if a prime divides a product, then it must divide one of the things in the product. That's all it says. So if $p=3$, let's say, and $p\mid (4)(9)(16)$, then $(3 \mid 4) \lor (3\mid 9) \lor (3\mid 16)$. Possibly more than one. If $p=2$, then $(2 \mid 4) \land (2\mid 16)$ But it must divide at least one.
Fundamental Theorem of Arithmetic, what is it? Here it is. Sometimes it's called Unique Factorization Theorem. So that's why we use the abbreviation UFT. We’ll see that FTA will be reserved for another fundamental theorem later in the course. So what does UFT say? What does the Fundamental Theorem of Arithmetic say?
$\text{Every integer}\, n \gt 1\, \text{can be factored uniquely into a product of primes.}$
I say uniquely here, I actually don't mean uniquely. I mean uniquely up to reordering of the primes. So I should be a little bit careful here, I'll update that in the PDF. So every integer, $n \gt 1$ can be factored uniquely into a product of prime numbers up to reordering of the primes.
So for example, if I have the number $6$, right, I can write that as $2 \times 3$, or I can write that as $3 \times 2$. Those really aren't different. I mean those should be the same thing, you shouldn't count that twice. So up to that reordering, $6$ can be uniquely factored as $2 \times 3$, the prime numbers $2$ and $3$.
Something else to mention, by convention, primes are just said to be a single element product. This is really just a technicality. You could include every integer $n \gt 1$ is either prime, or can be factored uniquely into a product of primes up to reordering, that's fine too. This is just usually the way it's stated, so I'm going to leave it as so. Okay. So again, what's the idea behind this? So I always use this analogy, if you factor a number in Canada, and your buddy in Australia factors a number, you should have them put the same factorization into primes, up to reordering of the primes.
Let's see the proof. So existence. Before I go through this proof, existence: you can prove this by the Well Ordering Principle or by Mathematical Induction. If you've seen one way in class, I suggest you should pause the video and try using the other principle. Challenge yourself, see if you can actually do this. But for now, let's just talk about the proof existence and uniqueness. The proof will be in red.
Assume towards a contradiction that not all numbers can be factored into a product of primes.
So there's going to be some number, some numbers, that cannot be factored into a product of primes. So the set of all numbers that can't be factored into primes is non empty. Well because it's non empty, well:
By the Well Ordering Principle, there must be a smallest such number say $n$. Then either $n$ is prime (a contradiction), or $n$ is composite.
So if $n$ is prime that's a contradiction, right? Again, we said primes are just single element prime factorizations, that's fine. Well what's the alternative? Or n is composite.
Since $n$ is composite, we write $n=ab$ where $1\lt a,b \lt n$.
So what does that mean? Well,
By the minimality of $n$, both of $a$ and $b$ must be able to be factored as product of primes.
$1\lt a,b \lt n$, so they satisfy the statement, or the hypothesis, of the Fundamental Theorem of Arithmetic. So I must be able to factor them into a product of primes.
This implies that $n=ab$ can be factored into a product of primes, contradicting the definition of $n$
But that doesn't make sense because we said that $n$ couldn't be factored into a product of primes, and that's a contradiction.
Hence every number can be factored into a product of prime numbers.
So that's part one. I mentioned nothing about the uniqueness here though.
So how do we deal with uniqueness? And that can be done as follows. So here I'm going to do an informal proof of uniqueness. In class I decided to do a formal proof and after some pondering I thought well maybe I should do the informal proof in class now. Maybe save the formal proof for later. That being said, let's take a look at an informal proof of how this works. I feel like you're going to get an idea of how the uniqueness part of the Fundamental Theorem of Arithmetic really works. Like the existence proof, this proof will be in red
Suppose that $n$ can be factored in two distinct ways.
So it, you know, it could have been more. Maybe I shouldn't even use the word distinct. Maybe I should say suppose $n$ can be factored in two ways. okay? And I'm going to prove that they’re the same. That's what's going to happen.
We can write $n=p_1p_2...p_k=q_1q_2...q_m$
Again, all these numbers are prime. I don't know if $k=m$. I'll try to figure that out as I go through this. But that's the idea here, okay?
Now let's look at the first prime $p_1$.
Since $p_1 \mid p_1p_2...p_k=q_1q_2...q_m$, by the Generalized Euclid's Lemma (Generalized Primes and Divisibility), $p_1 \mid q_j$
Since $p_1$ divides a product of things, so $p_1$ must divide some element in that product, okay? So $p_1 \mid q_j$.
By reordering if necessary, we have that $p_1 \mid q_1$.
So what do I mean by "reordering if necessary"? Well $q_j$ is just some arbitrary element in this product, right? So let's say $q_j$ was something like, I don't know, the $10th$ term, right? Well I'm going to move that $q_j$ to the first term, I'm going to move $q_1$ over to where $q_j$ was. So what am I doing? I’m basically renaming things. So $q_j$ was once called Tom, now I'm going to call him Harry, okay? That's basically what's happening here.
So I can assume without loss of generality that $p_1 \mid q_1$ because if it didn’t, then just move the terms around, right, reordering. That's the reordering part of the uniqueness, right? So remember they're unique up to reordering. So if it wasn't the first term, then just reorder it so that it was the first term.
Now dividing by $p_1$ on both sides we get:
$$p_2...p_k=q_2...q_m$$Now hopefully after seeing this, you can say, “Oh okay, well I can just keep doing this,” and the idea is yes that's the idea behind the uniqueness proof of the Fundamental Theorem of Arithmetic, just keep repeating this argument until you match up all the primes. By the end we'll know that $k=m$, and that each prime is equal to each other up to reordering. We might have to keep shuffling the primes, but that's okay. And that's the idea behind the Fundamental Theorem of Arithmetic.
So again, it's just a useful result, that numbers can be factored into primes. We'll see some applications next week and throughout the course we'll see applications of the Fundamental Theorem of Arithmetic pop up. But that's the main idea.
So where are we going now in the course? Maybe we'll give you a little bit of a spoiler alert, so next week we're going to talk about gcd’s. We're going to kind of enter the number theory part. So this is more of the proof basics part, first $16$ lectures of this course, and then from here on out, we're going to actually use this in the context of number theory. And our goal in number theory will be to head towards RSA encryption, so kind of how we communicate with banks online and other industries, and then from there, we'll go into complex numbers and talk about the algebraic properties of complex numbers.
That's it, I think that's all I really have to say. Again induction was the main topic of this week, so focus on that. So for the winter 2016 offering, that was also our “midterm line”: induction. So we don't need to know the Fundamental Theorem of Arithmetic for our midterm, but you do need to know up to induction and including induction. So thank you for your time, hopefully this helps you and best of luck.