welcome to another video in this video we're going to talk about something called proof by mathematical induction and even though it might sound like a really weird cooking technique induction is the idea of if i can prove for the next idea the next term the next term the next term i create a proof that's very similar to knocking over a domino and having to knock over a lot of other dominoes induction is the idea of prove one prove the next one and if you prove the idea of the next one you can always iterate that further further almost like recursion but in the future so we're going forward instead of going backwards now here's what the mathematical induction does and then i'll show you why it works as we go through because at first it's going to seem like that shouldn't prove a darn thing but i'll explain it to you why it does so here's how induction works number one you have to show that at least one term is true so we're going to show that whatever we're trying to prove is true for at least the first term so we're going to show that n equals 1 is actually true then what we're going to do might seem a little fishy the next thing we're going to do is assume that it's true for some other number not 1 but something between 1 and n whatever end is that might look a little funny um but here's here's what it says it says if you show the first one then you're going to assume it's true for some other term so n equals k now what what's the k k could be anything k could be the second term or the third term or the fifth term the 500th term or some other number so we'll assume it's true for something else so we show it's true for one we assume it's true for another one and then we show it's true for the next one well now what would the next one be the next one would be whatever is after the one you just assumed so hang on a second if i assume the third true term to be true then the one that would actually be four if i started to assume the seventh term one after that would be eight if i assume the k term is true the next one would be k plus 1 the one after it and this will actually prove the truth of whatever you're trying to show and we'll talk about why that is as we go through it one thing to keep in mind this is kind of fun and this is where sometimes it makes your brains but wait a minute you would assume this and assume it to be true for fact treat this step as fact it's important otherwise you can't finish your problem i always like to treat my assumptions like fact anyway but here we actually get to do it which is kind of fun i'm going to walk you through it there's there's no more to explain you show first you assume one more and then you show the one after that and that's how mathematical induction can be quickly summarized so we're going to do two examples and i'll show you exactly what i mean this is probably the most important thing is treating as this assumption like fact so here we go first to maybe get an idea of what's going on so what is this actually saying this is one three five seven nine odd numbers the sum of odd numbers is equal to the number of the term one number of numbers squared whoa really yeah that's true so here's what we're going to do we're going to show the first term like n equals one you know all right well what would that mean what that would mean is add up the first odd or odd number that would be one is that equal to the number of odd numbers squared that would be the first odd number squared yeah one actually does equal one that shows that that's true we've proved the first term true now i'm going to go a little further but you wouldn't have to i'm just going to show you so you get a feel for how this this series actually works um now keep this in mind what i'm doing is not additionally proving i'm not doing that i'm just showing you the formula this does nothing to prove it you could show how everybody wanted you'd have to ultimately show that the next term is true well you can't do that right like you can't keep going forever so at some point we'd have to stop we'd run out of time in our lives to show every single iteration of uh imagine the 500th odd number being added or the 5 billion well you can't do that you have to set up a series of dominance and say if i can show that the next one's true then the next one will always be true if the next one's always true then there's no stopping that falling of the dominoes so let's do this how about this how about adding up the first two odd numbers that would be one plus three is that equal to these are two odd numbers and this two notice what we're doing the first two odd numbers should be found by plug in one that's one plugging in one then two that's one and three and then plugging in two here that's two squared four does equal four that is really kind of cool if you wanted to find the sum of the first 50 odd numbers just take 50 and square it you have it we're proving that's true right now i'm gonna do two more just so you the feel how about the first three odd numbers the first three odd numbers would be one plus three plus five i've added three odd numbers three squared is nine that's nine that's nine how about adding the first four odd numbers one three five and seven is that equal to the first four odd numbers squared so four numbers four squared that would be the four odd numbers and adding and these are the values of the odd numbers that would be 16 that is 16. it actually does work now i'm going to say this one more time you could do this forever and it still wouldn't be enough proof to fundamentally prove that that is true you would have only shown it for a finite number of values what we need to do with deduction or what we intend to do with the notion instead of this idea that if i can now prove that the next one will always be true then i can use that to say well the next one's true but then the one after that will be true and then one for that will be true we can only do that by assuming something and proving the next one that's our next two steps so in general we just show this and then we go okay let's let's assume it's true for another one too we've actually shown several more but this is not enough to assume it's true for a general next one so this is step one right here and step two is now that you've proved one of them let's assume it's true for something else now that something else could be anything past the first one it could be the second term or the third term or the fourth term or the fifth term but in general we would just say okay if this was true for the first one let's rewrite this but let's assume it's true for some other number now it looks funny in saying let n equal k all it's saying is assume this which is based on n is true for some other term call it k what would that mean what that would mean is like i showed 1 plus 3 plus 5 plus 7 is the same thing as four squared i would show one plus three plus five plus seven plus all the way up to whatever the k is is going to equal k squared that's what it is it basically it replaces end with k but the idea is more important than that the idea is what you're doing is you're saying yeah that worked for the first one is it going to work for a second one or a third one or a fourth one well let's assume it will we showed three of them but we'll let's assume it will let's show that maybe it's not the fourth term maybe it's the seventh term then i show one plus three plus five plus seven plus nine plus eleven plus thirteen plus fifteen all the way to wherever i wanna stop is equal to that number by numbers squared so we say assume it's true for k okay well let's let's just go up to that specific term and say yeah that's going to equal k squared it's more important than just replacing this it's understanding i'm showing this for some other term past one pass your first one if it was 50 i'd do 1 3 5 7 all the way 50 equals 50 squared whatever the 50th odd number would be um 99 it'd be 99. so i'd show that all up to 99 it would equal 50 squared i hope that makes sense to you i hope that you understand that i've shown the first one i hope you understand what this actually means it's not just replacing it with k it looks like it but it's saying assume it's true then this would be valid for some other number k some other term k now the most important part we are going to treat this like fat this is true so whenever we see it come about and we will this is going to equal k squared we can use that we can use it so the last thing we do is now we need to show this we set up a series of dominoes and say the next one is true the next one is true the next one is true so we need to show this for k equals us or n equals k plus 1. well now what would that be if i show this for n equals k plus 1 then what would happen is i would take this and i would stop not at k but i'd stop at k plus one that's the next one that's showing that next one's always true well you can't stop that if you show the next one's always true then when you get to one you're sure the next one's true but when you need that one the next one's true when you get to that one the next one's true it will go forever and you'll always be able to prove the next iteration is true the next term is valid this holds for the next term so here's what we would do we're going to take this and go okay if i stopped at k i would stop at k minus 1. all right okay sorry 2k minus 1. but if i go to the next term now i'm going to take and not plug in k that's what this was i'm going to plug in k plus 1 to there so this is stopping at k we're assuming that's true this is stopping not at k but notice we have one more term we have let's stop at k plus one so this is the idea of the next term i hope that you're seeing that we're taking this and we're going one more further than where we stopped here for this one we said let's plug in k let's assume it's true for when we plug in k okay and now we're saying let's go one more than that so we're not going to stop at plugging in k that's here we're going to stop at the next one plug in k plus 1. well that'd be 2 k plus 1 minus 1. that would be the next term now what should that be equal that should equal k plus 1 quantity squared showed it for the first one assume it's true for some other one and now based on this based on that that that's true show for the next one so plug in this assuming this is true here's the whole idea if you can assume that this is always equal to k squared then wherever you see it this part is this part we just want one more term so why would it be appropriate to say if this part is this part and we know that this is true because we assumed it if we know that's true then this is k squared well we have one additional term okay let's maybe distribute that 2k plus 2 minus 1. this is 2 k square k squared plus 2 k plus 1 and so is that if i distribute it that shows that this side equals this side and it's shown that if i have an additional term if i have the next term that the formula still holds true so this is showing that provided i can prove it up to one term the next term will be true now here's why this works because you might be going this is fishy because you're assuming something's true you haven't proven yes but we sort of have remember this will hold true for any next term and since we've shown one term wouldn't this hold true for the term after that i.e the second term yeah it would so if i just had this let's make k equals 1 the next would be 1 plus 1 the next term so if i can prove one term if this is always showing the next term is true then i've already shown one term this holds for term two but wait it holds for term two i can show the next one holds return three well wait a minute if i hold if i show term three then this holds for the next one do you see how i'm knocking dominoes over if i show just the first domino and i show that it's true for the next domino and i use a general term not to show here but show it in general that i'm knocking over the next domino and then the next one and then the next one and then the next one it will never stop that's how induction works so even though it seems a little fishy like wait a minute you're assuming something you haven't proven that's true but we're basing on the fact we've proven one and showing it that the next one even if i start with that one i just proved is always going to be true thereby going forever as this true true true knocking down thing this this um array of dominoes falling over and that's the way induction works so show one assume for some other one and then show the next one treating this like fact because we've already shown it for one and it sets up the series of falling down and that's kind of cool we can always use this as true it'll show up somewhere when you're solving it um as hey replace this with that and then you show that both sides are equal let's do the same thing here but we're going to be a little bit more concise about it i'm going to do the very minimum to show you how the induction works so number one thing with induction if you're trying to prove this by the way this would prove all of the the formulas for your series that you would get improve all of them sometimes it takes a little more work but it would do it so let's show the first one does it hold true for one so if i plug in one i would get one is that equal to 2 times 1 squared minus 1. remember i'm showing the first one because i have to have somewhere for this domino to start somewhere to say yes but i prove the next one will be true what's the one after one two i've proved the second one's true what about after after two let's prove the next one's true so i've proved the idea of the next one being true so is this true if n is one one would that equal two times one minus one that's one yes this is true i have now proved the start that my dom my first domino can fall over that's too many s's assume it's true for something else so assume is true for like the second one or the third one or whatever one we use k to represent the idea of another term so something else besides the first one we're going to assume that that's true and then show that it keeps on falling show that the one after that would be true so we've assumed it's true for something else then it will hold and now we're proving an idea we're proving that the next term will also be true given that this one was true so if this was true the next one's true now why is that okay well we've already shown that one's true so showing that that's true given that then another one will be true the second one given that the next should be true we're proving an idea a concept okay well if that's true then what we're going to do is we're going to go all the way to here we're going to show that in terms of k and then one more so all the way to here and then the next one we need to show this we need to show this exact thing because it will come up again we just did it and then you need to show the one after that how you show the one after that is you you evaluate it's basically composition you take k plus one and you replace that with k plus one you've already placed it with k now go to the next one so it's four k plus one minus three over here we do the same thing but remember you're replacing with k plus one now you're talking about the next term that's how this series is added it says take however many terms you have plug it in there if i went to five terms i plug in five and five if i went to k terms i plug in k to k that's what we did right here now i'm going to k plus one terms i'm going to plug in k plus one and k plus one show the first assumed it assume this is true for some other term besides n and now based on that assumption we said assume this is true take it as fact assume uh show it for the next one so if i show for the next one i take k plus one i plug it in here that would be the next term and that would say based on my series i have to evaluate k plus 1 and k plus 1 because that is a term that i am now showing to be true so that's what this says here's the k here's the next term k plus 1 just evaluate it and then that would equal well the k plus 1 term inside of my cell so k plus 1 squared minus k plus 1. hopefully you see where that comes from because now we're going to make make use of that assumption we're going to say if this is true and we showed it for one of them if that's true then this piece this piece right here it is 2k squared minus k so that means this piece is also 2k squared minus k this i can distribute i can simplify a little bit and you know a couple things but what i would recommend is get to this point all combined and then distribute that just see if they're the same that's really the whole point is make sure that both sides are the same what that's doing is showing that the next term is still validated by the sum that you thought it would be by the sum of that next term so you're showing that they're equal satisfying the idea that the next term is true watch your signs there that's minus k minus one that's it those are true you've now shown that if you can start with one term being true and you've assumed the next one's true then the second one has to be true but then the third one has to be true because you've shown it in general for the idea of the next term that sets up that whole sort of waterfall idea where it's just going to keep on falling and falling and falling i hope that you have a better understanding for what mathematical induction does that you understand that it actually works it seems a little funny when you when you first see it but after that it really is a very powerful way we can prove a lot of these series that we find in this class and in calculus 2. so i hope that you enjoyed it hope you have a better understanding and i will see you for another video