Prove that 1+2+...+n = n(n+1)/2 for all integers n>0. (Hint: Use induction.)

Let us procede by induction:

First case: n=1. Then LHS (left hand side) = 1 and RHS (right hand side) = 1(1+1)/2 = 1. Therefore, we see that the statement is true for n=1.

Now, we carry out the inductive step: Suppose the statement is true for n=k. Using this, we attempt to prove that the statement is also true for n=k+1.

Set n=k+1. Then RHS = (k+1)(k+2)/2 and 

LHS = 1 + 2+ ... + k + (k+1) = k(k+1)/2 + (k+1) [Here we have used our inductive assumption, now we must show that this is equal to our RHS above.]

= (k(k+1) +2k+2 )/2 =( k² +k +2k +2 )/2 = ( k² +3k +2 )/2 =(k+1)(k+2)/2 = RHS.

So, we have shown that if the statement holds for n=k, it must also hold for n=k+1. Since we know it is true for n=1, we conclude that it is true for n=2, 3, 4, ....

Can you think of a different way to solve this problem (without using induction)?

(Idea: 1+2+...+n = 1 + n + 2 + (n-1) + 3 + (n-2) +... = ( n+1) + (n+1) + .... What happens if n is odd/ even?)