Video 0-3: §0.3 Mathematical induction, Towers of Hanoi

0:02 In the next section, I want to briefly talk about uh mathematical induction and about uh statements that have uh a free variable that already cropped up in the set example. Uh these are the most most interesting kinds of statements, and we will usually use those for algorithms because we want to make a statement for all possible inputs. So, we can have statements that have a parameter or a variable, and we'll we'll write these as uh in this in this notation of a function A of X. An example you could think of is X is an even number. Now, I can I can talk about uh A of 6 being true or A of 5 being false, and so on. You can put in any number.

0:45 If you have such a statement, you can wrap it with a quantifier that tells you something about what this X should be. The point is A of X itself doesn't have a truth value. It depends on X. So, you can only say whether it's true or false once you tell me what X is. But, another option is to say, "Is there any X so that A A of X is true?" And usually, we want to be clear about what universe X is coming from. So, we often specify a set. But, this is implicit here. So, the set is kind of known. So, this symbol exists means there's some X so that A of X is true. In our case with even numbers, of course, there are even numbers. So, not a very interesting statement. Uh the other version of that is flipped around. A is stands for for all. And that means it has to be true for every X in a certain universe.

1:42 And uh if we pick it pick as the universe the natural numbers, and our statement A of X is an even number, then of course, for all X A of X is not true because there are non-even numbers, odd numbers.

1:58 Again, you can uh you can if you want, to just deal with one of the two. You can write for all as not exists an X where A is not true. Or the other way around. So, one of the one of the two is enough. And uh what makes these interesting is you can nest them. And this is the part that I definitely want you to be able to read even though um that specific example is is not so relevant for us, but this may be the most likely you've seen. So, any kind of analysis class would talk about limits. And the usual way these days to formalize a limit is this epsilon-delta criterion. Where you say, if you have a function F what does it mean for F to approach a limit value A as X goes to some some value psi. That means for every tolerance epsilon you pick there's a distance delta so that if your X is close enough to psi, namely closer than delta, then the function value is within the tolerance of the of the limit value.

3:03 Okay? But the important point here are the two quantifiers. You can't flip them around. It's important that they have this order. For every epsilon there is a delta that may depend on the epsilon. If you were to flip this around, it's a much weaker statement and wouldn't define a sensible limit. Okay?

3:28 So, we'll occasionally encounter statements like this or even maybe in disguise because whenever we talk about an algorithm being correct, we want to make a statement for all inputs. And so, we definitely have a quantifier there. And if we talk about running time, we'll often use asymptotic notation which has nested quantifiers in it. So, you'll you'll encounter these even though they're sometimes hidden under definitions.

3:57 How can you prove quantified statements? Uh for the exist existential, it's very simple. If you want to prove exists X so that A of X is true, you find some value some concrete value uh and I use xi here again where this is true. So, these are not too hard. You just find an example. For the uh for all statements, a few more options exist. And let's see if uh if done this before.

4:38 Uh I'll hope to get through this one quickly. It doesn't need any thinking. And this question is mostly testament to the diversity of of this group. Um all of those who who have an undergrad degree in computer science will definitely have seen it, but the vaguely remember might be you. Uh that's what I thought. And then there's a smaller group who has never seen it before because it's something more important in discrete math than in say engineering fields. You often don't do it induction that much because it's not as useful.

5:25 Right, let's leave it with that. Um I mean, it kind of it kind of means I'll go too fast for the last group and too slow for the first group. Uh but it seems seems impossible to uh to do it better than that.

5:48 So, for all statements are like this, just what we just had. Um one strategy that sometimes works is you you say I let X be an arbitrary but fixed value, and then you just show your statement A of X based on that. Sometimes you can do such a direct proof. But uh if that doesn't work, then induction is a powerful a powerful way to prove such a statement if the quantification is over a discrete set. And uh let's pick the natural numbers here, but there are extensions that make this a bit stronger. Um which we'll not get into too much. So, suppose you have a statement for all natural numbers something is true. Then what you can do by the principle of induction you prove it for A0.

6:39 You uh you prove that A0 is satisfied. We call that the basis. And then you show that if you're at some point on the ladder and you have proven AN is true, that you can jump to the next step of the ladder.

6:59 And this is in the form of an implication. So, for every point on the ladder, for every number N there's a uh a sequence of steps starting from A0 and then using these implications to arrive at the truth for A of N.

7:17 Now it at first, if you if you haven't seen this before, it looks like you're replacing something simple for all X A of X is true with something more complicated. In particular, we have another quantified statement here and so on. So, it looks like um this is not not helping you at all. And you'll do a detailed example in in the tutorials. Um last year the last bar of the group was much bigger, so I did an example in class, but I think I'll I'll skip this here because 80% might find this uh not too insightful. But, you'll do a detailed example of induction proofs in the tutorials on uh on an example um that's that's simple enough to follow uh with some uh recursive definitions.

8:04 And I want to briefly give you an intuition why induction helps. So, the the big step here is instead of having to prove A of X without any other help, what we're proving in the inductive step is based on the statement being true at a certain point, we just have to make it one bigger. And that gives you a lot more power because you can use the truth of that statement. It's kind of pulling yourself out of the swamp at your own bootstraps. It's a it feels sometimes almost like cheating because inductive proofs sometimes don't give you much insight why a statement is true, but they're in fact they're of a totally valid formal proof that the statement is true.

8:54 The basic version of induction is what I've shown you. You start with A0, and then you go from the previous step one step further. You can strengthen this argument so that instead of just the last the statement for N, you can use all previous statements and derive from that the next step. That's also fine. And as I alluded to earlier, you can uh you can use other things than natural numbers in there, but this I'll I'll mostly just list for reference uh for the computer science grads who have seen that. Um we won't use that very much.