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

0:00 <Untitled Chapter 1>

0:03 yeah let's talk about mathematical induction as one of the slightly less obvious proof techniques or proof strategies which at the same time can be very powerful specifically in discrete mathematics and computer science

0:21 induction is all about Quantified statements I've briefly alluded to this earlier but let's introduce the the notation and the Notions for that properly uh because this is again something that pops up many many times and this is very well uh worth knowing Beyond this module the first thing we need is statements that have a parameter so it's it's basically a placeholder for something some object a number in this case I'll write a of X for a statement that has something to say about this value X and that could be from our example X is an even number now obviously such a statement can be either true or false depending on the value of x so it doesn't make sense to say proof a of x right I can prove a of 4 or a of 7 but the statement a of X itself if you want it's more like a function for every value of x it tells you a Boolean value a truth value yes or no true or false but not by itself it is is it true or false we can turn it into a logical statement that has a true or false value using these quantifiers and they basically tell you what you're supposed to do with this variable X and there's two that are really useful

1:48 Existential and Universal Quantifiers Existential

1:48 existential and Universal quantifiers existential means there must be some value of x so that a of X is true they exist some X so that a of x and we write this with this little reverse E I don't know where the symbol comes from but it seems a good mnemonic to say e like exists exists X so that a of X holds and the other one don't ask me where this symbol comes from is this this little angle I don't know uh

2:26 upside down a yeah that's a good one yeah yeah okay like that yeah how could I not miss this thanks okay upside down a stands for all it stands for for all either way ah well all x a of X should be true now you can immediately imagine imagine that that kind of statement is very relevant for algorithms because we usually want to say they are correct no matter what the input is that's saying for all inputs the algorithm does the right thing and we'll have to talk about the second bit what that what that means so yeah let's highlight that a bit uh these are the statements we very often deal with as often with these logical statements it can be convenient to have all of them just to be more expressive but we could do with just one of them by rewriting saying that a is true for all X is the same as saying there's no X so that a is not true right I think that's intuitively clear enough

3:35 so you could always just use all or just exist now the tricky bit is when we start to Nest things you can have statements that have not just the dependence on one variable X but on 5 or as many as you wish and that's where things get really powerful but also a little complicated and we have to be careful about the order of the quantifiers I wanted to put a real example there just to make make it clear even though okay I hope that most of you have seen the formal definition of the limits of a function or the limit of a sequence um in in this case here what we're talking about is some function X it takes a value and it spits out a value and we could try to prove some some properties of that function like continuity or uh is not an analysis class so um you don't have to get into this in much more detail but we want to say as X approaches some some specific value because I is some number that you fix it's not a variable as X approaches this value the function value approaches some other number a okay we'll often use this or asymptotics we'll see next unit so not much not much use to talk about it now

4:08 The Limits of a Function

5:00 we'll we'll use this full stop um what does this mean that the function has this limiting value this is one of the things where historically mathematicians played with this for a long while with infinitesimals and and trying to do this intuitively and I mean it's probably fair to say that in some instances they fell flattering their face by not having a rigorous notion for this and what people came up with as a rigorous notion for the definition of this limit is this the Epsilon Delta Criterion it says uh you tell me for every Epsilon how close do you want the function value to be to the Limit value you tell me how close you want it there exists a Delta I can tell you a Delta so that if x is closer to XI than Delta the function value is closer to the to a than Epsilon so nested quantifiers uh often can be phrased as this kind of game for all means opponent's choice you have no control exists my choice I can I could pick one now the tricky bit is the order matters uh having you choose first and I can react to that is different from you choose first I choose first and you can react to me very obvious in games uh who starts

5:33 The Epsilon Delta Criterion

6:02 Nested Quantifiers

6:31 matters and so for quantifiers you have to read them left to right another way to say this this Delta is a function of Epsilon it may depend on the choice of the quantifiers to the left okay

6:54 Limits of Continuous Functions

6:54 all right we won't really talk about limits of continuous functions very much we'll basically apply this for asymptotics how does a a function or an algorithm behave if n becomes very big in that sense we'll use limits um this is more for background than just to make make very clear these quantifiers can be nested the order matters and the inner variables can depend on the choice of the outer ones

7:23 okay right here yeah it's the way to build powerful statements um uh for example here okay let's move on simple statements to prove are the existential ones if you have a statement exists X so that a of X you just find one X and B Mary that's often simple because you you get to choose what the value is and so it's a simple proof as the ones in the previous subsection uh the trickier bit is the for all statements and um that's where we go to the main topic of this section so let's see how many of you have seen seen this before

8:44 yeah yeah you can prove it by contradiction foreign yeah okay so I I guess the the question would be if if I claim for all this heart why don't we just rewrite as an existential um we could we could do that and then we have the negation so we could do proof by contradiction the thing is you would have to prove that any choice leads you to a a contradiction and that any choice that that seems hard right whatever choice you write down I could say okay it failed for your choice but I have a different one maybe it's fine for that one so you still have this I have to go through all cases I don't think you can get rid of that uh induction is a way to get rid of that in a specific sense you'll see um good I think that's enough a lot of people have seen that so maybe um

9:05 Proof by Contradiction

9:54 yeah I'm um maybe I'll do an example but a quick one then you'll do an example in the tutorials but let's let's first about let's first talk about the statements so we're talking about for all statements these are the the tricky ones for all x a of x um and now I'm thinking of X not being any real number but it has to be something discrete so the easiest case is natural numbers okay so the statement here asks has to say something about natural numbers yep

10:54 okay question is can we can we somehow rescue some bits of induction for the reels hi I mean depends uh let's let's first talk about deduction uh if the real state if the statement is is fundamentally about continuity continuous things then no but there might be sometimes tricks I don't know I think I think the answer is no if you can then you can reformulate the statement

11:24 um so sometimes we write this restriction as or X in n0 or something like that so that's if you want it's a shorthand or saying for all x x in the natural numbers implies a of X okay uh that's logically the same thing uh this is more convenient to write so we often in a way this is about mathematicians and types often doesn't go well together mathematicians are very very sloppy when it comes to types compared to programmers who are used to the strict typing of most programming languages so when a mathematician writes for all it's usually assumed that the reader the human on the other side knows or figures out what the possible values for X are it often doesn't make sense that here x is a square or uh a motorbike it you usually have a clear notion of what x can be and it's not a sin to express that implicit thing explicitly right what is the set that X can come from

12:41 uh that said I'm also sometimes sloppy and it's convenient to leave things out um if you don't have to write as much so I'll sometimes write things like this as well in the hope that the the range is clear but um it should always be possible to write down the exact range without thinking too hard

13:00 what does induction do induction does two things you prove the statement you want to prove for some sorry that's that's not the part of induction uh one one way to prove a for all x a of X statement is you prove the statement without assuming something about X

13:25 that's sometimes possible sometimes this is convenient I think it's mostly it's a bit dangerous usually you need something about x uh so this is in principle possible sometimes doable a direct proof uh it's a bit dangerous induction can be a little more convenient yep

14:09 tell you in in some easy cases when you see that the statement doesn't really depend on X much or something like that yeah yeah so that's why I listed it sometimes sometimes it's doable induction is a way when it's not so easy and they're um if we have say the natural numbers from zero we would prove as one thing the statement for zero and then prove a different for all statements but one that gives us more ammunition to prove we prove that for every n if we have the statement for one number that implies the statement for the next bigger number and those two things together are enough to prove the statement for all natural numbers and you can people often draw a ladder where you you know you start at zero you build this this first little piece of the letter and then you show whenever you whenever you can build a ladder up to a certain height you can get the next Higher One by adding one more one more Pole

15:20 and so you start with zero and you prove that you can always make a step and by always making a step you get to any any fixed height okay that's the principle of of induction uh in this in this strict version you're only allowed to use a of n to prove the next bigger number this is actually a bit restrictive you can also just use all previous statements used that the statements are true for all values up to the one that you currently look at and then prove the next bigger one sometimes people make a distinction and call this simple induction weak induction and this strong induction or complete induction I don't care too much uh is is both induction there's not not too much of a magical difference you can extend the principle a bit more we won't really need that here but you can essentially apply induction whenever something is constructed step by step you can start from something and then you can make it bigger and maybe um a natural thing for us in computer science and in this module we'll talk about binary trees so one way you can apply induction there is you can say a binary tree is a leaf or it's a node with two sub trees which are binary

16:44 binary trees so that's again the way you can start from one thing and then build up if you can do that you can imply induction question 50. I think the extinction

16:52 Question 50

17:07 and except for any subset has a small value set for which and it totally well that's it for me any sort of that respondent value yep and moving amplify for multiple previous statements might be different it might be used that maybe in they really not sufficient to 2 PM to respond I think

17:51 um statement will reach more complex sequences for which the next value if you never does not depend on your previous value yeah I think the distinction between this this weak induction and the strong induction is a little uh it's a little academic if you if you want I think you can reformulate your statement so that it includes all the previous ones and then formally you apply the other induction if you care so much uh I don't think that's the the key thing here it's what's surprising is that you can basically bootstrap yourself inductive proofs sometimes when you read them you you look like yeah I think that's solid but I've learned nothing about the statement apart from the fact that you formally proven it right which is remarkable often a proof is assumed to convey a lot of knowledge and insight into what you're proving something about inductive proofs need not be like that they can be uh completely ugly in the sense they teach you nothing but they work and I I mean if the the goal of the proof is to prove something they're really effective

19:12 um so yeah sometimes it's much easier to come up with an inductive proof than any other proof shall we do a quick example what are people's thoughts uh I guess there's two-thirds that say ah don't bother me I've seen that and the other thirds a bit lost at this point

19:39 I'll do a compromise I'll do an example and run through a little quick so that we can cover the rest uh let's see uh I think a nice example is the towers of Hanoi um I think many will know this so it's a puzzle it has some story behind it but I think this is all made up by mathematicians and so without you know uh think of your favorites mythical mystical setting an Indian temple some Vietnamese thing or uh what else I've read it in a monastery and some you know some Hideaway Place High up in the mountains or whatever uh the game has three poles and has discs sorted in size and the the goal the goal is to get the entire pile to a different Pole but you can only move one disk at a time and you're not allowed to ever put a bigger disc on top of a smaller disk and then usually the story is well these priests monks whatever they have to do this and once they finish the world comes to an end uh and well whatever so the the most original story I read was that they have 64 pieces stacked on top and so when they finish this the world comes to an end and the question for you

21:05 is should we worry right and so let's try to answer that question how many steps do we need to move this 64 pile from one pole to the next if you've seen this before okay I know it's maybe has lost its magic if you've seen it if you see this for the first time you start playing with three or so and you figure out yeah okay you could do this right you can um

21:44 you can put the the top one here and it's gone from there then you can put this one on the other top now you're all blocked but you can get the smaller one from here put it on top there and then I can actually move this lower one to the last position now I have to think a bit ahead if I place this here I can go with that one there so let's took the take the smaller to the side middle one up here and then finally that one on the top good easy to do with three if you do it with five you get already a bit bored and lost and you you move a few pieces around because you you messed it up if you do it with 64 how many pieces what's the minimal number of steps does anyone know you remember minimum number of steps

22:43 uh unfortunately not this time because well we could we could do first the other it's hard to spoil up I I feel for you it's it's annoying to spoil a puzzle but I think I have to um so let's let's transform that into an inductive statement we want to say about something for all sizes it's it's kind of easier to solve the general than the specific one in this case so let's say we have n disks foreign [Music] the number of steps we need if we have n disks

23:30 is drum roll 2 to the N minus 1. and so as a computer scientist you should know that 2 to the 64 minus 1 is not to worry about if you so integer overflows if you count up in a loop a 32-bit integer you might over might see overflow a 64-bit integer you will never see overflow in this universe all right that's the so that's the answer to the very practical side of this puzzle uh the poor monks will never finish I think it's 500 billion years or well something like that uh takes takes basically forever in physical terms but how would we possibly prove such a statement by induction

24:20 so we would start with the in troduction base the base case is let's be really lazy let's say no discs uh I have not to do anything so the answer should be zero

24:38 zero steps are needed and two to the N minus one that is zero if I put in a zero here brilliant so that's the base case done right and now we do the inductive step

25:03 Inductive Hypothesis

25:06 the inductive hypothesis that's how people often call this that's the an and this is our statement a of n so let's assume that we already know for n disks it's exactly 2 to the N minus 1 steps that I need and now comes the the brilliant little insight

25:36 if I have my tower there's one more disc at the bottom and then a tower of okay this is uh this is even below my standard of drawing ask say something how do we move this pile of disks from here to here well three steps we take

26:03 this large bit move it here that's step one then remove the red part to here that's step two and then remove the gray one back easy right one two and three how many steps do I need for that the red one is a single step easy the other two are the inductive thing with just n uh one smaller so if we start with n plus one disks then uh the number of steps or n plus one disks

26:54 plus one and the rest is arithmetic because now we can use the inductive hypothesis to replace this by 2 times 2 to the N minus one and then you see that this works out to two to the N plus one minus one all right and that's the end of the proof I you see in this case you actually did learn something about the problem because this is a recursive algorithm and you could actually implement it by a recursive function just like that no much thinking needed but also um see how knowing the solution for the one smaller problem was really all we needed here and the proof became quite simple whereas if you try to prove all of this directly from from nothing it's also doable for this puzzle but it's more it's more tedious and needs more insight up front whereas the induction here guided you to what you had to do all right good that was towers of Hanoi in five minutes yep

28:09 yeah yeah so that's a good point so the the question is can you somehow instead of just using induction for proving what you already know discover what you want to prove I think it's a it's the Achilles heel of induction is no uh not really uh usually induction doesn't help you discover what you have to prove sometimes it can work iteratively you try with some statements and you try to prove it and then you see you're you're stuck you're missing something and that can sometimes give you the Insight of what that missing bit is and then you can add it to the statement and then uh then it goes through but it's not really like a clear structure yep induction doesn't really help you much if you don't know what to prove it can just be super thirst and and quick if you do