Video 1-3: Mathematical Induction

0:01 Now in the next section, we look at the first more interesting statements. So far it was essentially just combination Boolean combinations of um uh elementary statements. And now we'll look look at more complicated statements and more complicated ways to prove them. And the most famous of these is called mathematical induction. Or at least the most famous for computer science applications where things are discrete. Uh before we get there, let me say what this what I mean by more complicated uh statements. Uh remember so far we had things like A meaning it rains now and B meaning the street is wet, things like that. Now I have statements that have a parameter or in the uh voca- in the terminology of of mathematical logic, it would be a free variable. X is a placeholder that can take different values. And I can have statements like this that uh some value X is an even number. Now whether that's true or not depends a lot on what X is. There's numbers that are even, there's numbers that are not even.

1:10 So I can write write things like uh A of 10 and that would be true. Or I can say A of 5, which is not true. So maybe I say not A of 5. Uh and now the statement depends the the truth value of a statement depends on what value I insert for this variable X. And here I'll just write this as if it was a mathematical function where you you call that function with a specific value.

1:42 If I have such a statement with a parameter, I can add these quantifiers around that statement to make again a statement that just has a value true or false and nothing in between or it doesn't depend on any parameter. Here in A of X, X is a free variable and here it's bound again by the quantifier. And there's two flavors that we often use. The existential quantifier says there is some example for X where A of X is true. And for any other values, A may be false, we don't care. So there exists some X so that A of X is true. And some here means unspecified number. Could be one, could be many. And the universal quantifier for all uh says that for all X, A of X must be true.

2:34 You can reduce one to the other. Um for all X means the same as there is no X so that not even if you just spell it out in English, uh that works. So we can deal with just one of the two. Uh what is important and slightly implicit in my notation here to keep the slides a bit more uh clean, I should normally specify what are allowed values for this variable X. Are these all natural numbers or maybe all real numbers or are these all binary trees or um all inputs to some algorithm. Usually you will want to specify that. So we might say for all X in the natural numbers, I could say 2 * X + 1 Let me say here an N. The convention that I'll also follow I want to say this is not even. So I could make this little sentence. Okay, now I'm I'm breaking my rule. I should always write N0, not N.

3:50 Uh the convention in this in this module will be X tends to be unspecified what it is, but N should be a natural number if if nothing else is said or maybe an integer. Negative numbers are fine, but only whole numbers. Um then I could say this, for every natural number it is true that 2 N + 1 is not even.

4:15 Maybe we can agree on that. Now, uh things get even more interesting in when you start to combine several quantifiers and there the order is very important. Uh who has seen this epsilon-delta criterion as the definition of a limit of a function? Or as a function Yeah, limit of a function is the evil thing.

4:40 This is analysis 101, something like that. Never seen it? Then um let me briefly spell it out for you. So, you know about functions. This could be a function mapping uh real numbers to real numbers. Uh you could take derivatives or you could discuss where are local minima, these kind of very same functions as you did in high school as well. Um now, you could ask if a function is not defined at a certain point, you could ask what happens there and that's where we usually want uh a limit.

5:17 And this this limit value A could also be infinite or it could be uh minus infinite or it can be a concrete number. So, the classic example I guess is is things like uh uh this this fabulous term. Of course, this function should be one everywhere. But the way I've defined it, it has a problem at X equals 2. It's not I can't I'm not It's not allowed to to divide by uh two. And so, uh it really has a problem at this at this point.

6:05 And if someone gives you a function defined like this, you should not simply assume that you were allowed to plug in x equals two.

6:14 Who knows what that person had as an intention? Maybe this is mathematician's glasses on. We want to be very picky about exactly what is written down and not make any assumptions that are not somehow justified. Uh you could still ask if you plot this function, then at any value that is not two, it will be just one. Right? If I insert zero, then it's minus two divided by minus two. So, I end up at one. And it'll always be one, but at this very point here, I'm supposed to not evaluate it. It's a rather boring function, and wouldn't it be useful to be able to say it still has essentially the value one at this point, too? And that's what the limit allows you to say. So, this is undefined, but uh I'm still allowed to write the limit as I approach this.

7:20 And I can define um I I can ask whether that's the value I suspect it is, and in this case it will be. And formally, how do I define what this means? Writing this this limit. Intuitively, what we mean is as as I get closer and closer to this bad point that I'm not allowed to plug in, I'm get I'm getting closer and closer with my value to this limit point. In the case of this function, it's entirely boring because it doesn't do anything uh here. We could modify the function a bit, but maybe that's beside the point. Um the formal definition says for every epsilon, for any small real number greater than zero that I want to be away from this uh target value, there is some delta, some uh difference in the other in the other direction, so that when I'm with my value that I'm looking at closer to uh this limit value xi, two in our case, when I'm closer than delta to this limit point on the x-axis, I'm closer than delta to the limit point, then the function value is at most epsilon far away from the target uh value, the limit value, so in y y direction.

8:41 And the order matters in in so far that this delta can be uh a function in epsilon. I'm allowed to choose a smaller and smaller delta as I make epsilon smaller. Uh if you think about it, this is important here that the quantifiers are nested in this way.

9:00 Okay, that's a rather complicated statement. This is usually about the level where where people start to get confused. Uh three nested quantifiers and the wheel starts spinning. Um at the opposite end, a very simple statement, if I'm just claiming there is some x so that a of x is true, all I'm asking you is to find an example for x that makes this true, some value xi so that a I a of xi is true. That's the easiest. Now here already the statement is somewhat tricky to write down. We'll not deal with limits a whole lot, or at least not at this very formal level. Um we'll practice it a few times in the tutorials and then uh assume that this is okay and we'll jump to a slightly higher level of abstraction. Uh but we will be concerned with uh statements of this form a lot. Uh because what do we want to prove usually in algorithms is uh one of two things, either that an algorithm is correct, that it produces the correct output, or that it takes as only a certain amount of computational time or resource, could also be space.

10:12 And this is usually a statement for all inputs such and such is true. For example, for all inputs, I get the expected output. And that's almost um that's almost always such a for all statement.

10:34 Before we move on, let me ask a bit how much exposure you've had to induction. So, in general, it's a bit hard to prove these for all statements because you're supposed to prove something for infinitely many options. So, it's out of the question to just write them all down. And it's fair to say in general, this is just hard to do. Now, in computer science, usually the things we care about are discrete, so they're I can stick numbers to. I can write them down in an infinite list, but still one after the other and I don't miss anything. Uh so, like the natural numbers or uh other discrete objects, graphs and trees, all of these are innumerable or countable. And for those, um there's a trick how you can sometimes get these proofs much easier, and that's induction.

11:33 Uh no need to hide this. Um among the people I think we were not many more in the previous question. Uh, so most people have seen it before, so I'll only um, refresh your memories. And we will do some exercise tutorial uh, some some exercise problem in the upcoming sheet for next week. It'll coming out the on Friday and you'll work over this next week where you can do uh, a few more practice uh, proofs with inductions.

12:05 >> So as I said, in general it's hard to prove these for all statements and induction often makes it a lot easier by giving us more to work with. Um, the only other option really that is general is assume nothing about your value X and just prove that this statement A of X is true without making any assumptions on X. And if that works, then you're a lucky person and you you proved your statement uh, for all X A of X. And then the the other option is when X is discrete and for simplicity let's say X is a natural number. Then an inductive proof works as follows. You prove that the statement is initially true for the smallest object. Smallest natural number is zero. That we call the inductant the induction basis or inductive basis. And then you prove this slightly more complicated looking statement but which gives you more power in in your assumptions. For every N, if A of N is true, then it's also true for one larger object.

13:12 N plus one. And this is an implication, so you can use all of those uh, proof templates that we had before. And the magical thing about induction is that you're allowed to assume what you're trying to prove in part of the proof. So, it feels like you're doing this somehow cyclically and cheat. But, of course, you're not cheating because you're starting with a smaller value and push it one level higher. So, if you wish, you can say there's a a ladder that you climb up in your proof. And you start with A0 where you do have do have to do the actual work and show that the statement is true. And then the general step is that you're able to climb up to a certain point up the ladder up to this point. And you prove it is possible from there to reach the next uh of the of the steps and you can climb one further up.

14:05 If that if those two things are true, then clearly you can reach any position on the ladder if you're only patient enough. This is the simplest and cleanest form of induction. You can slightly strengthen it in two ways. Um one is sometimes called complete or strong induction where you're replacing here the A of N with all of the previous values. It's You can prove that these are the same um from the the set of statements they're able to prove, but often this is a bit more convenient because you have more at your disposal to make the uh implication work. And the second is um a generalization that we won't often use here, but I want to mention it once in a while. Um yeah, not well-funded well-founded, huh? Should be. Wohl wohlgeordnet Noethersche Ordnung auf Deutsch.

15:22 Uh this is the most abstract or most general sets of objects on which you can do induction. All that it says is you have somehow objects that you uh work with. And you can compare them. They're bigger and smaller. And in a way there's always um a smallest object. Any sequence of of objects from this universe if uh it has decreasing values, it gets smaller and smaller, is only finitely long. So, there's no infinite strictly decreasing chains in this in such a well-founded um set of objects, the natural numbers are such. You could start with any natural number. If you make it smaller, eventually you reach zero and then you're you're finished, you're stuck. Or say you have a a tree, a binary tree, and you count the number of of vertices, you can start with any tree. To make it smaller, you get rid of some of the nodes. Eventually, you're left with the empty tree. And then you can no longer get further smaller.

16:24 So, all of these are well-founded sets and you can do induct induction on all of those.