Video 0-3: §0.2 Mathematical induction

0:00 Mathematical induction

0:01 In the next subsection, we want to look at a slightly different type of statement where we do need some different templates for proving them. And most famously, it's mathematical induction. There's a few smaller ones hidden in this section as well.

0:17 Quantifiers

0:21 The new type of statements I'm referring to are quantified statements. And that's where these these weird symbols come into the into the game. These are called quantifiers. And they for them to make for for those to make sense, we need statements that have a parameter, something like like this. So, if I write A of X, I mean this is a statement where there's something variable, this this X that occurs in it. And the statement could be true or false, it really depends on X. Like if I put in X equals 4, then the statement is true, but if I put in 3, it's false, so it depends, right?

1:04 I can take such a uh uh parameterized statement and stick an existential quantifier in front of it. Then I'm turning it into a statement that says there is some value for X that makes A of X true. So, in English, there exists some X so that A of X holds true. And I can do this for all symbol, another quantifier that turns the statement into for all X, A of X is true. And uh well, often we want to restrict X to a certain range or certain set.

1:44 This one, you want to repeat you want me to repeat what I said on this slide? Yeah. Um We can have statements with parameters. So, it's a statement that is true or false depending on what you plug in. There's something X in this case. And if X is 4, the statement's true. If X is 3, the statement's false. So, it doesn't make sense to ask if A of X is true or false. It only makes sense after you substitute X with something concrete. These types of parameterized statements can be decorated by putting one of these symbols in front. And then it makes sense to ask for the entire statement whether it's true or false. And the two The meaning of these two is there exists at least some value for X that makes the statement true or for all possible values of X, the statement is true. Okay?

2:41 Yeah, it's important concepts. If you haven't seen these symbols in some math classes, these are really occurring a lot, not just in our in our module. It's it's useful to know those. Again, we can restrict our attention to one of the two. We can say for all can be written as there is no X so that A does not hold, so that's the same as saying for all X, A holds. Um But still for proving statements, um this doesn't usually help you very much. Uh you need different strategies for the two types of statements. I want to mention um this concrete example of a statement involving several quantifiers because it's it's a famous one, it's a very important one, an interesting one. I hope many of you have seen it before. Uh but it also illustrates some um some corner cases that makes these uh quantifiers a little tricky. Uh so, what what this statement with this formula here uh formally says is there's a certain function that depends on a parameter X.

3:51 And we want to say as X approaches a certain value xi, the function approaches a value X. So, the limit of the function as X goes to xi is A. Uh you could have uh xi could be plus or minus infinity and and same for A, so there's some some extensions of this, but it also works with concrete numbers. Limits are everywhere in math. And people argued for a long time uh how to formally deal with this, and the definitive answer is is the epsilon-delta criterion. So, you say that this this statement is this is the same as claiming uh for every epsilon of an error that you allow between the function, the actual function value, and A. So, you're at the end claiming that the function must be closer to A than epsilon. For every such error bound you give, there is a delta so that if X is closer to xi than delta, the function value is closer to A than epsilon.

4:58 Okay? So, epsilon and delta are just ranges on the X and Y scale if you if you plot the graph of this function. But it's important that the order of the quantifiers is as given. For every epsilon, there is a delta, and this delta can depend on epsilon. It usually does. Okay? You've all had some analysis class, real analysis at some point, I I guess. It just might be buried in your memory. Uh all right. We're not really building on this definition so much. It's just an example how quantifiers can be tricky. Okay? So, don't don't get too uh obsessed with the details if if they're not clear. For this unit, we're talking just about the proof templates. So, uh we don't want to get too involved in any of these uh problems.

5:56 A simple template is for the existential quantification. If you have a statement there is an X so that A of X holds, well, you just find an example and be merry. So, you try to find one value for Let's pick our example from above. If this is your statement, uh I I'll say you pick X equals 4, and then the statement's true. Job done. Okay? So, existential is usually easier. Uh the tricky one are the um the for all statements. So, before we come to this, let's see if you've seen induction before. Again, computer science undergrads uh will have would have seen this up and down, I guess.

6:50 As I said before, I think around half to two-thirds of you are are not CS undergrads. That was the numbers from last year. I'll check the details from the from the survey for for Monday.

7:21 All right. Just few people missing, but I guess it's fair to say that half of you have seen it and are still comfortable doing it. Um most of you have seen it with a few exceptions. Uh but maybe not everyone's completely ready and set to go if I would give you something to prove by induction. Uh which I think we'll do next week in the tutorials, so uh you'll be all on the same page after that.

7:50 Recap

7:52 All right. So, let's do a recap what this uh mystical mathematical induction is. As I said, it's all about proving the for all quantified statements. The existential quantification is is not so tricky. So, if you have a statement like this, um one way to go in general is you assume X is some arbitrary value that you know nothing about, and you try to still prove just from that that A of X holds. If you can do that, then you've proven for all X, A of X. That has nothing to do with induction. That works in principle, but also it's a very weak template because it gives you hardly anything. Uh it's just a way of of writing down a proof. Um If you can if you additionally know more about X that X is from, say, just the natural numbers, uh an integer and starting from some range, say from zero, then you can use induction.

8:53 And for that, you prove two things. First, you show that for the smallest value in in your range, zero, the statement is true. That's called the induction basis. And then you show this slightly more complicated statement using one of the techniques uh that we've um seen before. So, um for this for all, you would probably have to use this first this first um bullet. And then you have an implication, which we've talked about at length. Now, uh it might seem on this formal way of describing things, it might seem like we go from a fairly clean statement for all X, A of X to something much more complicated. Why on earth would that help us? Why should we torture ourselves like this? Uh but the the trick is that the more complicated statement gives you more to start your proof with because you're proving an implication that assumes the same statement you're trying to prove just for a smaller parameter.

9:55 And that's often um very powerful to make the next step. It's almost magic sometimes. You can just guess a solution and prove it correct by induction. That way you get a formally proven result without having any intuition into the into why it it holds. Uh so we'll we'll have a an example in the tutorials. Another one, the standard one that you often see is uh the little Gauss formula, the sum of the first n integers. All right, you you know about this one. So, if you sum from one up to n i So again, this this summation formula uh this summation symbol is probably known to you, but uh just in case. So, this is a shorthand for writing uh 1 + 2 + 3 and so on up till n. And it's like an integral, you see there's a starting point, there's an ending point, and then you sum up a certain uh term.

10:58 And there's a closed formula for this thing, which is n * n + 1 / 2. young uh Gauss discovered this formula in his primary school days when his teacher allegedly wanted to keep them busy for some time, and he just finished it after a few minutes. I don't know if that's that's true, but it's a lovely story, and that's uh maybe good enough by itself. Now, for this form for this formula, you can find very nice uh intuitive explanations why this is true. For example, write the sum uh out uh once, and then write it again below, but in reverse, and then you notice that the terms uh match up and uh have the same sum all the time. But there's also an easy way to prove it by induction.

11:55 Um looking at the time, maybe I I don't do that in detail here. I think this is repetition for almost all of you. And you'll you'll practice in uh induction in the tutorials again. So, you can ask Ben if you feel like you need more more preparation on this.

12:18 I want to highlight two things. Um this form of induction is sometimes called the or the the the weak induction, if you want, uh and it's uh contrasted to the strong induction, where instead of just assuming A of n for the last the last parameter, you can assume it for all the previous values together.

12:40 And the template works in pretty much the same way. So, the in the intuition behind induction in in both cases is you start with A0, which you have proven true uh in the induction basis. And then you from that you get an implication that A1 is true. And so, now you know two things, and from that you can derive that A2 is true, again by this implication that you've proven here. And so, you can build up this ladder of statements uh at it to infinity. And then the principle of of induction says this is enough to prove the statement with fall.

13:26 There are more fancy versions of induction. Just uh to mention this, that it's not restricted to natural numbers. Um and discrete math computer science often uses these kinds of statements. Uh I don't think we'll we'll need it in this class, so I just wanted to mention it, put it on the slide, so that you can Google the term if you want. You can use induction for any other recursively defined object, where you have something like um a size that is never below a value and only goes up in a in a somewhat structured way. Uh the formal thing is you need a well-ordered set, but okay.

14:05 We don't need that detail.