>>11308603Our claim: 1+2+3+···+n = n(n+1)/2
First, we need to show that the claim holds true when n=1. This part is usually not very hard. On the left hand, we only sum the first term, so we just get 1. On the right hand, we have n(n+1)/2 which is 1(1+1)/2 when we substitute in 1. This simplifies to 1*2/2 = 1. Since both sides are equal, we've shown that the claim is true when n=1.
Now for the tricky step. We need to show the following thing: if we ASSUME the claim is true for some number k, THEN we need to show that the claim is true for the number k+1. The assumption we're making is called the "inductive hypothesis." We don't know whether our assumption is true yet - we only will when we complete the induction and the things we've proved cascade upward over all the positive integers.
So, let's assume that for some k, 1+2+3+···+k = k(k+1)/2. We want to show that, if n=k+1, 1+2+3+···+k+(k+1) = n(n+1)/2. What is this right hand side? It's (k+1)(k+1+1)/2 after substituting.
So let's see. If we start on the left, with 1+2+3+···+k+(k+1), because of our inductive hypothesis we know that 1+2+3+···+k = k(k+1)/2. So let's write this in: 1+2+3+···+k+(k+1) = k(k+1)/2 + (k+1). We can pull out a common factor of (k+1) here to see that k(k+1)/2 + (k+1) = (k+1)(k/2 + 1). Now we can pull out a factor of 1/2 from the second term, which goes from (k/2 + 1) to (k+2)/2. So we have (k+1)(k/2 + 1) = (k+1)(k+2)/2. And finally this is (k+1)(k+1+1)/2 which we saw was n(n+1)/2 for n = k+1. So we've finished this step, we've shown that 1+2+3+···+k+(k+1) = n(n+1)/2 where n = k+1, i.e. we've shown that our claim holds for k+1 after we assumed our claim held for k.
Now we know k can be any number, and we've shown the claim for 1. So by the principle of induction, the claim is true for any number by the sort of chain reaction we discussed before. This finishes our proof.
