Lecture 11

[Music] so now let us start with a new topic which is principle of mathematical induction okay all of you have know what is recursively defined function on natural numbers you remember that yeah you start somewhere and then you have a rule how to go forward and then the principle of mathematical recursion or principle of recursive definition of functions will allow you to define a function on entire Omega or natural numbers at that same time we said that to define something for all natural numbers we need recursion and to prove something for all natural numbers we need induction so this is the uh exercise for induction what are the main steps that you had to prove it for base case right so base Cas is uh in this case it's zero uh one yeah and then from the base case like there is another induct induction case like if you know the statement is true for M then you prove it for m + one okay and you just have to write it down properly all of you know how to do this what about the second one will this work will this same idea work anybody who has finished second one we can support for two Bas cases just okay even if you assume for two base cases yeah I mean you can do finitely many base cases by hand I don't have any problem but then what will you do and then 2 for n you you are assuming what you're assuming that it is 2 for nus 1 and nus 2 and then prove it for yeah so assuming it for n minus1 and n-2 and proving it for n is this really a valid method of proof can you assume it only for some specific numbers that you want like only previous two cases can you assume that why not we assuming only for the previous one case the same thing no I mean when you are saying that uh here we are only assuming it for one case and then proving for for the next then assuming two cases and then proving for the next they are same but that needs a proof that these two methods are the same see if I want to prove a statement for m + 1 and I assume the statement for all numbers less than m + 1 and using that I can prove it for M +1 then I should be done but in mathematics this is called strong induction weak induction is when you have one step induction it's a domino effect all of you know dominoes yeah dominoes are like dyes yeah so if you are if you have arranged dominoes in a sequence if you drop the first one then the first one will topple the second one second one will drop the third one so it's a chain effect ladder effect however this one step effect is called weak induction and when you assume it for everything below it below that number then it is called strong induction so let me write down um these two properties so uh here we have to we can use weak induction and the method of proof we need here is called strong induction okay so let's do that what is principle of weak [Applause] induction I'm just going to call it w of P for a property P I want to prove something like the property p is true for all natural numbers starting from a certain stage so therefore I'm going to write it weak induction principle for property p w of P okay my starting step could be called k0 so I'm just going to write down what what this says yeah so if P of k0 is true this is my base case and for all M bigger equal K 0 whenever the statement p is true for M then I can prove it for m + 1 then then from this entire thing I can conclude that in fact the statement p is true for all natural numbers uh sorry maybe I should for all natural numbers bigger equal k0 the statement p n holds any problems reading this statement base cases true and onestep induction cases uh true then I can get done the conclusion for all yeah recursion also had a similar principle if I know how to define the next step using the previous steps then I can Define it for all yeah the so on part same thing this is our principle of weak induction and on the other hand and let me write down the principle of strong mathematical induction I'm going to call it s of P for a property P okay so again it starts similarly suppose it is true for p of uh I mean suppose property p is true at K 0 some base case and for all M bigger equal k0 now I'm not assuming just PM but I'm going to assume a big conjunction big and yeah so I will say k not less equal J less equal m and PM so so I'm assuming that all the things from K KN like the property P holds for k k + 1 dot dot dot up to PM whenever this thing happens then PM + 1 is true that oh yeah PJ sorry thank you this should be PJ then pm + one is true and whenever this happens like the base case and the strong induction hypothesis is true then we can again conclude that for all n bigger equal k0 PN is true so which of these two statements is stronger well doesn't the name suggest that now this is weak induction this is strong induction so strong induction should be stronger but it's not they are both in fact equivalent whatever method of proof you may use yeah you are going to get the same answer okay so this is our main job today that we'll prove that these two statements are equivalent but before we do that yeah we have to understand a bit of rules of logic because what does it mean that principle of strong induction implies principle of weak induction let us discuss that so you are given the principle of strong induction and you want to prove this what does it mean to prove this the principle of weak induction what is the meaning of proving it for property P using a series of implications to get that using a series of implications and what is given to us see the principle of weak induction or principle of strong induction are both statements of type A implies B right so a implies B this is also a implies B this is also C implies D let's say okay let me write it down we are going to uh use these statements so this is of the form a implies B and this is of the form C sorry not here C implies d a itself can be broken down into two pieces yeah a z and a bar okay so this is my uh a z and this is my a bar and this is my c0 and this is my c bar so a z stands for base case C 0 stands for base case of strong induction and this is the these are the inductive steps okay so when we say that we want to prove a implies B then what should we start with exactly we should start with a and then prove B okay so whenever we are showing uh like so we want to show strong induction this should be the easy part right strong induction should imply weak induction as the name suggests so strong induction implies weak induction so first of all we have to choose a property so property is p Okay so assume for a property P of natural numbers that strong induction like s ofp holds i e I mean I'm just going to call it CP implies DP holds yeah C is a statement which has p as a parameter p as a variable so therefore I'm writing it as CP and implies DP you agree with that okay and to prove weak induction to Pro WP with we should also assume what should we assume a of P okay so what are we given now we are given a of P then we are given C of P implies D of p and we want to prove B of P but also note yeah I mean this is a note here here so note that b of p is same as D of p is there any change in B and between B and D no so it will be sufficient so what are we given C CP implies DP is given AP is given and we want to prove BP which is same as DP now there is a rule in logic which we'll study in logic part properly so this rule is called modus ponents MP it says that if Alpha is true and Alpha implies beta is true then you can conclude beta is true very good okay so what is our situation right now we know that c of P implies D of p is true and B A of p is true and want to prove that D of p is true so using modest ponents what is sufficient to prove just CP if CP is true then C uh using modest ponents CP is true and CP implies DP is true together will imply that DP is true okay so by MP enough to show that CP is true but CP is c c0 p conjunction c p okay so I'm writing this hopefully you have finished and I'm going to go back observe C is c0 conjunction c bar we want to show that c is true CP is true so when is a conjunction of those of two things true when both of them are true yes so we need to show so therefore we need to show that c0 P is true and c p is true everybody is with me still right okay so c0 p is true and C bar p is true what is c0 p observe c0 of p is same as a a z of p and that is given to you yeah since AP equal to a0 P conjunction a bar p is true both a0 p and a bar P are true moreover c0 p is equal to a0 p and and hence c0 p is true so I'm going to put a tick mark to this c0 of p is true we have proved that now what do we need to prove c p is true okay let us look at what is c p we need to show for all M bigger equal k0 whenever this conjuntion is true then p m + 1 is true so when we want to prove something for all M K bigger equal k0 we should choose some M and prove it for that and it will automatically follow correct so we should uh choose an m and then assume this side and then prove the right hand side Okay so to prove c p is true assume that for any M bigger equal K 0 this is true K 0 less equal J less equal n M PJ is true okay so all of these things are true conjunction is true means all of them are true so in particular PM is true in particular PM is true but what do we know from the previous screen if PM is true and PM implies PM + 1 is true then by modus ponents PM + 1 is true okay so by I'm just going to write by a bar p and MP modus ponents p m + 1 is true and therefore we are done yeah therefore a bar therefore c bar p is true you understood the idea of the proof okay it's long but straightforward once you understand rules of logic yes okay so C 0 p is true that's clear so c p is true because uh what what is CB let me go back here we are supposed to assume the this part for for any M bigger equal k0 if I assume the left like the implic left hand side of the implication I need to prove the right hand side okay so I assume that the left hand side is true so that that big conjunction is true which means in particular PM is true because it's in the conjunction now now PM is true okay now go to a bar so a bar says that for all M bigger equal k0 if PM is true then PM + 1 is true and you know PM is true therefore PM + 1 is true therefore this conclusion of c p is true and we are done okay very good so use the assumtion that this not less than J less than n is true we use this assumption and then we prove yeah because this whole sentence see unlike any uh science theories mathematics is always about if this then that it mathematics never claims anything to be true okay science theories might do that theories of acids arenus is theory of acids and bases it will say that if this like this particular substance is an acid this particular substance is a base mathematical theories don't do that it always it's always uh what should I say very honest if this is true then that is true yeah we don't try to make any big claims so we us that is true so m m isal to K is is true and then we could have followed kind of rtion no we don't want to use induction to prove indu two two inductions are equivalent right yes I mean when you are when your M happens to be equal to k0 then it follows from c0 that the left hand side is of this implication is true and therefore the right hand side is true why why can't we do that like induction is an axium so it's not circular no I'm not trying to say it circular okay don't confuse anybody by saying that yeah I'm just saying that these two statements are equivalent yeah even if it's considered as an axium we still need to prove that these two are different aums but they are equivalent why can't we use induction to do that no no no we don't want to use induction to do anything okay so is this okay now the harder part slightly harder harder part is to show that weak induction implies strong induction so let's do that now so weak [Applause] induction implies strong induction however we cannot proceed directly we have to define a new property so given a property P Define a new property Q by Q of M for M bigger equal k0 if and only if conjunction PM uh PJ K 0 less equal J less equal m okay so we are not really cheating but observe this yeah so Q of M is defined to be this conjunction so the property is true for property p is true for k 0 K 0 + 1 dot dot dot up to M okay and we are only defining it for M bigger equal K 0 not doing anything so what we will show indeed is that so we will show that W of Q if W of Q is true then s of p is true understood see principle of mathematical induction is a statement which says that for all properties P of natural numbers the statement is true so I can choose something different like for proving property s of p i can use a slightly modified property Q to prove the same statement because there is a quantifier yeah for all properties P so for all properties p means in particular it is also true for Q for the same property we will prove s of P that's what you want to prove correct for the same property we have to Pro yeah p is given and I want to prove strong induction for p but I'm slightly modifying the property to q and I will assume the weak induction principle for Q okay now first of all I you all know that b of p is same as D of P let me go here B of P and D of P are same but now I'm going to claim that b of q and d of P are also same observe that b of Q what is Q it's true for all of them yeah I mean put here maybe I I should write it in a different color so if I'm saying for all n bigger equal k0 conjunction of K 0 less equal J Lal n of P of J is true this is logically the same thing as saying that for all n bigger equal K 0 P of n is true right I'm just saying it in a more complicated manner but it's the same so okay note that b of Q is same as D of P okay so like before we are given given that the principle of weak induction is true given uh that AQ implies BQ is true and CQ CP is true we want to prove that DP is true but DP is same as BQ is true now using modus ponents what is sufficient to prove AQ okay good so using MP it is sufficient to prove that AQ is true yeah because if AQ is true and AQ implies BQ is true then BQ is true and BQ is same as DP okay what is AQ once again yeah a z of Q well observe that please what is a z of Q Q c0 of c0 of Q or c0 of P both of them are same right uh look here what is the property it is here so that conjunction when m equal to k0 is just single turn yeah I mean it's just P k0 so a z of Q is equal to c0 of p is true yeah since CP is true so again the problem is only in the part a bar okay so what is a bar of Q yeah to prove a bar of Q is true assume for sum M bigger equal k0 that uh Q of M is true but what is Q of M look here Q of M is this conjunction that is precisely this part this is Q of M right so therefore if this is true for some M then what can you conclude p m + 1 is true so by C of P oh I should use black color again so by c bar of p and MP what will I conclude that P of m + 1 is true a sorry A P and M A Bar p and and P using the property of a bar p no I'm given C of p is true so therefore c p is true C 0 and C bar are true so I'm using C P and then modus ponents to conclude that p m + 1 is true please have a look here again yeah this is c bar and I'm assuming the green circled part okay so what is given that p of M +1 is true but what is finally but Q of m + 1 is actually Q of M conjunction so now Q of M is already assumed to be true we have proved that P of m + 1 is true and therefore and therefore qm + 1 is true so what did we finish proving therefore a bar Q is true and we are done so both the these principles of induction are actually the [Music] [Music] [Music] same [Music]