Property P conjecture

Transcription

I'm going to define a function S of n and I'm going to define it as the sum of all positive integers including N. And so the domain of this function is really all positive integers - N has to be a positive integer. And so we can try this out with a few things, we can 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 4, which is going to be 1 plus 2 plus 3 plus 4, which is going to be equal to 10. Now what I want to do in this video is prove to you that I can write this as a function of N, that the sum of all positive integers up to and including N is equal to n times n plus one, all of that over 2. And the way I'm going to prove it to you is by induction. Proof by induction. The way you do a proof by induction is first, you prove the base case. This is what we need to prove. We're going to first prove it for 1 - that will be our base case. And then we're going to do the induction step, which is essentialy saying "If we assume it works for some positive integer K", then we can prove it's going to work for the next positive integer, for example K + 1. And the reason why this works is - Let's say that we prove both of these. So the base case we're going to prove it for 1. But it doesn't always have to be 1. Your statement might be true for everything above 55. Or everything above some threshold. But in this case, we are saying this is true for all positive integers. Our base case is going to be 1. Then in our induction step, we are going to prove that if you assume that this thing is true, for sum of k. If we assume that then it is going to be true for sum of k + 1. And the reason why this is all you have to do to prove this for all positive integers it's just imagine: 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 are going to prove it for 1. We are going to prove that this formula right over here, this expression right over here applies for the case of 1, when n is 1. And then we are going to prove that if we know it is true for any given k that is true for the next one So if we know it is true for 1 in our base case then the second step, this induction step must be true for 2 then. Because we proved generally if it's true for k it's going to be true for k + 1. When it's true for 2, then it must be true for 3, because we have proved it, when it's true for k, it's true for k + 1. So if it's true for 2 it's true for 3. and if it's true for 3 it's going to be true for 4. You can just keep going on and on forever, which means it's true for everything. Now spoken in generalaties let's actually prove this by induction. So let's take the sum of, let's do this function on 1. that is 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 is just 1. There is no other positive integer up to and including 1. And now we can prove that this is the same thing as 1 times 1 pluss 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 1, so we have proved our base case. we have proven it for 1. Now what I want to do is I want to assume that it works for some number k. So I will assume 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 this function for k + 1. This is what I'm assuming. I'm assuming I know this. Now let's try to do it for k + 1. So what is the sum of all of the integers up to and including k + 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 are assuming that we know what this already is. We are assuming that we already have a formula for this. We are assuming that this is going to simplify to k times k plus 1 over 2. We are assuming that we know that. So we will just take this part and we will add it to k plus 1. so we'll add it to k plus 1 over here. And if you find the common denominator, the common denominator is going to be 2. So this is going to be equal to... I'll write the part in magneta first. so 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 2's would cancel out, I'd just wrote it this way so I have a common denominator. So this is going to be equal to... We have a common denominator of 2 and I'll write this in a different colour here. So we are 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 + 1. So let's factor this out. So if you factor out a k + 1, you get k plus 1 times refractoring out over here, if you factor out k + 1 you'd just have a k. Over here if you factor out k + 1 you would just have a 2. Let me colour code those. So you would know what I'm doing. So this 2 is this 2 right over there and this k is this k right over there. We factored it out. These k+1's we factored out is this k+1 over there. And it's going to be 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 k plus 1, that's this part right over here. Times k plus 1 plus 1. Right? This is clearly the same thing as k + 2. All of that over 2. Why is this interesting to us? Well we have just proven it. If we assume that this is true and if we use that assumption we get that the sum of all positive integers up to and including k + 1 is equal to k + 1 times k + 1 + 1 over 2. We are actually showing that the original formula applies to k+1 as well. If you would take k + 1 and put it in for n you got exactly the result that we got over here. So we showed , we proved our base case. This expression worked for the sum for all of positive integers up to and including 1. And it also works if we assume that it works for everything up to k. Or if we assume it works for integer k it also works for the integer k plus 1. And we are done. That is our proof by induction. That proves to us that it works for all positive integers. Why is that? We have proven it for 1 and we have proven it that if it works for some integer it will work for the next integer. So if you assume it worked for 1 then it can work for 2. Well we have already proven that it works for 1 so we can assume it works for 1. So it definetly will work for 2. So we get 2 checked. But since we can assume it works for 2 we can now assume it works for 3. Well if it works for 3 well then we have proven it works for 4. You see how this induction step is kinda like a domino, it cascades and we can go on and on forever so it works for all positive integers.