(idea) by Debbie Wed May 10 2000 at 5:45:58

An example of Induction 

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

Step 1:  Show true for n=1

(1) = 1  therefore true for n=1



Step 2:  Assume true for some n=k

Since we assumed it is true for some n=k we know that

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



Step 3:  Now show true for n=k+1

We know that the sum of (1+2+3+...+k+1) = (1+2+3+...+k+(k+1)) = (1+2+3+...+k)+(k+1)

now we can use our assumption from step 2: (1+2+3+...+k)=k(k+1)/2  
let's substitute this into our equation and we get:

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

Now if we distribute the k we get (k^2+k) + (k+1) 
                                   -----
                                     2

Now we simplify to get (k^2 +k+2k+2)
                        -----------
                             2

Which equals (k^2+3k+2)       (k+1)(k+2)    (k+1)((k+1)+1) 
              --------    =    --------   =   ----------
                  2               2               2

Therefore by induction:
(1+2+3...+n) = n(n+1)/2
I like it!