CMPU-145, Spring 2013
Proof from class
March 4, 2013


Theorem.  0 + 1 + 2 + 3 + ... + n  =  n(n+1)/2,  for all natural numbers n.

Proof.  By induction.

  Let P(n) be the proposition:  0 + 1 + 2 + ... + n = n(n+1)/2.

  Base Case:  P(0) is the proposition:  0 = 0(0+1)/2, which is true.

  Recursive Case:  Assume that P(k) holds:

        I.e., assume that:  0 + 1 + 2 + ... + k = k(k+1)/2.
 
        **** Note:  Our assumption that P(k) holds is called
                    the "inductive hypothesis".

     Prove that P(k+1) holds:  

        I.e., prove that:  0 + 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.

     Lefthand side = 0 + 1 + 2 + ... + k + (k+1)

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

         = k(k+1)/2 + (k+1), by our assumption that P(k) holds
                             (i.e., by the INDUCTIVE HYPOTHESIS)

         = (k*k + 3k + 2)/2, multiplying out and putting over common denom.

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

         = Righthand side!!

  ------------
    DONE!
  ------------