The general form of an induction proof of a statement S(N) about a natural

number N is:

1. Show S(N0) is true for some initial N=N0, this is called the base case

and N0 is often 0 or 1.

2. Show that if S(k) is true for some natural number k, then it is also

true for k+1.

3. Then as it is true for N0, it is true for N0+1, and then for N0+2, and so

on, so we conclude that for any natural number N>N0 it is true, as we can

connect it to the base case by a chain of step 2 above.

4. As we now have that S(N) is true for any natural N>=N0, we conclude

that it is true for all naturals >= N0.

Now your problem is to prove:

1+2+3.... +n = n(n+1)/2

for all natural numbers this is our statement S(n). We take as our base case

n0=1, when S(1) is the assertion:

1 = 1(2)/2 = 1,

which is true, so our base case is true.

Now we assume that S(k) is true for some k and show it true for k+1.

As we are assuming S(k) is true this is the assumption that:

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

Now add (k+1) to each side:

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

Rearrange the right hand side of this equation:

1+2+3.... +k+(k+1) = (1/2)k^2 + (3/2)k +1

..........................= (k+1)(k+2)/2

..........................= (k+1)[(k+1) + 1]/2.

But this equation is now S(k+1), which is:

1+2+3.... +(k+1) = (k+1)[(k+1)+1)/2.

So from the assumption that S(k) was true we have shown that S(k+1)

must also be true, combining this with the base case S(1) which we have

already shown to be true we may conclude by induction that S(n) is true

for all natural numbers n>=1.

RonL