If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains ***.kastatic.org** and ***.kasandbox.org** are unblocked.

Main content

Current time:0:00Total duration:9:23

I'm going to define a function s of N and I'm going to define it as the sum the sum of all positive integers positive integers integers including n including including n and so the domain of this function is really all positive integers and has to be a positive integer and so we can try it out with a few things we could take s of 3 this is going to be equal to 1 plus 2 plus 3 which is equal to 6 we could take s of let's take s of 4 well that's going to be 1 plus 2 Plus 3 plus 4 which is going to be equal to 10 so fairly fairly straightforward now what I want to do in this video is prove to you and there's actually multiple ways to prove this that I can write this as a function of n that the sum of all the positive integers up to and including n is equal to n times n plus 1 all of that over 2 and the way I'm going to prove it to you're at least the first way I'm going to prove it to you is by induction this will be a proof by induction it's kind of an interesting philosophical way to prove something because the way you do a proof by induction is first you prove the base case you prove the base case so in the case of this this function this statement right over here so this is what we need to prove in the case of this statement right over here we're first going to prove it 4-1 that's going to be our base case and then we're going to do the induction step the induction step which is essentially saying if we assume it works for some positive integer K that if so if we assume that then we can prove that it's going to work for the next positive integer it's going to work for K plus 1 and the reason why this works let's say that we prove if we prove both of this so the base case we're going to prove it for in this case we're going to prove for 1 prove for 1 but there's it doesn't always have to be 1 because you might your yours it might be this is true for everything above 55 or everything above some threshold but in this case we're saying it's true for all positive integers so our base case is going to be 4 1 and then our next F we're going to try to prove that if you assume if you assume 4 if you assume that this thing is true for some of K if we assume that then it is going to be true for some of K plus 1 and the reason why this is all you have to do to prove this for all positive integers is just imagine so let's think about all of the positive integers right over here 1 2 3 4 5 6 you could just keep going on forever so we're going to prove it 4-1 we're going to prove that this formula right over here this this expression applies for the case of 1 when n is 1 and then we're going to prove that if we know it's true for any given K that is true for the next one so if we know it's true for 1 in our base case then the second step this induction step says well it must be true for 2 then because we've proved generally if it's true for K it's going to be true for K plus 1 well if it's true for 2 then it must be true for 3 because we've proven if it's true for if it's true for K is true for K plus 1 so if it's true for 2 it's true for 3 and then if it's true for 3 needs to be true for 4 and you can just keep going on and on forever which means it is true for everything now spoken in general out generalities let's actually prove this by by induction so let's take let's take let's take the sum let's do this function on 1 well that's just going to be the sum of all positive integers including 1 is just literally going to be 1 we've just added all of them it's just 1 there's no other positive integer up to an including 1 and we can prove that this is the same thing as 1 times 1 plus 1 all of that over 2 1 plus 1 is 2 2 divided by 2 is 1 1 times 1 is 1 so this formula right over here this expression it worked for it worked for 1 so we proved we've proven our base case we've proven it for 1 now what I want to do is I want to assume that it works for some number for for some number K so I will assume I will assume true true for I will assume it is true for some number K so I'm going to assume that for some number K that this function at K is going to be equal to K times k plus 1 over 2 so I'm just assuming this is true for that now what I want to do is think about what happens when I try to find when I try to find this function for k plus 1 so this is what I am assuming I'm assuming I know this now let's try to do it for k plus 1 so what is the sum of all of the integers up to an including k plus 1 up to an including k plus 1 well this is going to be 1 plus 2 Plus 3 plus all the way up to k plus k plus 1 right this is the sum of everything up to and including k plus 1 well we're assuming that we know what this already is we're assuming that we already have a formula for this we're assuming that this is going to simplify to k times k plus 1 over 2 or assuming that we know that and so we'll just take this part and we'll add it to k plus 1 so we'll add it to the k plus 1 over here we'll add it to the k plus 1 and if you find a common denominator if you find a comment the common denominator is going to be 2 so let's go this is going to be equal to I'll write the part in magenta first this is K times k plus 1 over 2 plus 2 times k plus 1 over 2 this thing in blue is the same thing as that thing in blue the twos would cancel out I just wrote it this way so I have a common denominator and so this is going to be equal to this is going to be equal to we have a common denominator of 2 and I'll write this in a different color here so we're going to have K times k plus 1 plus 2 times k plus 1 now at this step right over here you can factor out a k plus 1 both of these terms are divisible by K plus 1 so let's factor this out if you factor out a k plus 1 you get k plus 1 k plus 1 times we fracturing it out over here if you factor out a k plus 1 you just have a K over here if you factor out a k plus 1 you just have a - let me color code those so you know what I'm doing so this 2 is this 2 right over there and this K this K is this K is this K right over there we factored it out this these k plus once we factored it about 2 this k plus 1 right over there and it's going to be all of this all of this over 2 now we can rewrite this this is the same thing this is equal to this is the same thing as this is the same thing as k plus 1 that's this part right over here times k plus 1 k plus 1 plus 1 right this is clearly the same thing as k plus 2 all of that over all of that over 2 now why is this interesting to us well we've just proven it if we assume that this is true if we assume that this is true and if we and then we you just use that assumption just use that assumption we get that the sum of all of the positive integers up to and including k plus 1 is equal to k plus 1 times k plus 1 plus 1 over 2 we're actually showing that that original formula that original formula applies to k plus 1 as well if you just take k plus 1 and put it in for n you could put it in for n you got exactly the result that we got over here so we showed we proved we've proven our base case this this this expression worked for the sum for all of the positive integers up to and including 1 and it also works if we assume that it works for everything up for up for up to k or if we assume it works for the integer k it also works for the integer k plus 1 and we're done that's our proof friend by induction that proves to us that it works for all positive integers why is that well we've proven it for 1 and we've proven it that if it works for some integer it's going to work for the next integer if you can assume it works for some integer it we'll work for the next integer so if you assumed that it worked for one then it can work for two well we've already proven that it works for one so we can assume it works for one so it definitely will work for two so we get two checked but since we can assume it works for two we can now assume it works for three well if it works for three well then we've proven that it works for four you see what how this induction step is kind of like a domino and it Cascades and we can go on and on forever so it'll really work for all positive integers