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. If we assume that then it is going to be true for sum of k + 1. Then in our induction step, we are going to prove that if you assume that this thing is true, for sum of k. But in this case, we are saying this is true for all positive integers. Your statement might be true for everything above 55. So the base case we're going to prove it for 1.

And the reason why this works is - Let's say that we prove both of these.

And then we're going to do the induction step, which is essentially 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. We're going to first prove it for 1 - that will be our base case. The way you do a proof by induction is first, you prove the base case. And the way I'm going to prove it to you is by induction. 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.

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. 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. And so the domain of this function is really all positive integers - N has to be a positive integer. 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.

Khan academy discrete math