Video 0-4: §0.2 Mathematical induction

0:00 Intro

0:03 in the next subsection i want to talk about mathematical induction that is a strategy to prove certain statements that are true for an entire range and it's often very challenging to prove these statements in a different way whereas an inductive proof can be amazingly simple to the extent that you've written down the proof and you still feel you don't really understand why it's true but it's a for it's a formal and mathematically correct way to prove statements it's very well spread very well uh used and you should definitely know about it

0:45 Quantified statements

0:46 so what does that look like first of all it applies to quantified statements so these are statements that talk about a whole range of statements really so we now have statements that have a parameter it's not just a or b it's a of x and an example could be x is an even number we have implicitly used that before when we were talking about the proof that that n squared is odd and then n is also odd um the uh

1:20 we we had the parameter n and effectively we we used it in in this sense but we didn't make it so explicit because the proof could just work for any number any odd number n and it was the same proof we just had to pick a different k sometimes life is a bit more complicated so here we want to explicitly say that it's a statement that is a statement that depends on this number x if we have such a generic statement a family of statements we can do two things we can put an existential quantifier in front of it and that's the statement that there is some value of x so that this statement is true that's something we sometimes need so you just have to find one example where it's true then this statement is true exists in x so that a of x holds

1:47 Existential quantifiers

2:19 the more more complicated statement but more useful one as well is the universally quantified one where you have this for all x so this uh this symbol is is also called exists and this is called for all so that's the statement no matter which value you give to x a is true and often people write things like this for every x in r greater or equal 0 a of x or something like that so you often you often explicitly list the range of values for x that are allowed here so if if the statement only makes sense for for non-negative numbers you could write it like that

3:06 Nesting quantifiers

3:08 um there's a formal equivalence between these two if uh if you have the statement for all x a of x holds that's the very same thing as saying there is no x so that a of x does not hold same thing but again sometimes proving one thing is easier than the other so it's it's helpful to be able to flip around these negations and uh what makes quantifiers really helpful in mathematics is that they can be nested to come to express uh fairly complicated statements you might have seen this before if you've gone through an analysis class if we have a function x and we say that as x approaches a certain value x i this function has a limit of a so the function approaches a if you get if x moves close to psi you can express this formally of saying for every epsilon that you're still away from a so that's how far do you allow the function to be away from a for every such accuracy parameter if you like there exists a delta there exists

4:27 a distance on the x range so that when x is close enough to psi maybe closer than delta also the function value is closer to a than epsilon and here it's very important that these quantifiers are ordered in that way because it means that delta can depend on

4:56 epsilon so that's the understanding if you nest quantifier like this then whatever comes inside can depend on all the variables that are further to the left okay good proof strategies for quantified statements if the statement is an existential quantified statement it's fairly simple you just have to find an example that uh makes the statement true it doesn't need a real strategy usually it's just finding an example

5:28 Inductive proof

5:31 it's more challenging for the all quantified statements one thing we've implicitly done before in in the n squared proof was this you fix an arbitrary but fixed value for x and then you derive that a of x is true that's what we did before the other option is you use an inductive proof and that's uh the new thing so um pay attention here you prove two things you have to prove that um so this is this is only possible if the range for x is the natural numbers or it can be slightly generalized but here let's pick natural numbers only the numbers 0 1 well maybe i should mention this so that's the numbers zero one two blah blah blah blah blah arbitrarily big including the zero you show that the statement is true for zero and you show a different all quantified statement you show for every n it's true that if a of n holds then also a of n plus 1 is true and that's the inductive step it's a bit like climbing a ladder

6:30 Inductive step

6:54 you start with a0 that's the first part and then you apply the inductive step to get from a0 to a1 because you put if you set n to 0 in this statement you have a an implication a0 implies a1 but we know a0 is true so it implies a1 but a1 then implies a2 and you can go you can climb all the way up to infinity not physically but in terms of a mathematical proof this is this is a valid step to do

7:28 there's slight generalizations to this instead of just using the last statement you can use all previous statements so all the statements with the parameter smaller than n and show that that implies uh the next statement and you can generalize the idea of induction a little bit to other sets um and other discrete objects uh we won't make massive use of this but it's it's worth mentioning at this point now you will see in the tutorials another example of how to use inductive proofs you might have seen classical examples like this in discrete mathematics classes we'll you will have some chance to practice this a little bit