CS212 Problem Set 2 (Spring 1999) - Written Exercise 1
Written by Brandon Bray

Prove: 1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2

-----------------------------------------------------------------------

P(n): 1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2
Claim: P(n) is true, for all n >= 1

Proof by Induction on n

     BASE CASE: n = 1
        1^3 = 1^2        [This is true]

     INDUCTIVE STEP: Let k >= 1
        Assume P(k) is true:
          1^3 + ... + k^3 = (1 + ... + k)^2    [Induction Hypothesis]
        Prove P(k+1) is also true:
          1^3 + ... + k^3 + (k+1)^3 = (1 + ... + k + (k+1))^2
     
        LEMMA:
          1 + 2 + ... + k = k*(k+1)/2
          {See Induction Examples Web Page for proof of this equality}
     
        1^3 + ... + k^3 + (k+1)^3
            = (1 + ... + k)^2 + (k+1)^3       [by I.H.]
            = (k*(k+1)/2)^2 + (k+1)^3         [by Lemma]
            = ((k^2)/4 + (k+1))*(k+1)^2       [by Distribution]
            = ((k^2+4k+4)/4)*(k+1)^2          [by Fraction Addition]
            = ((k+1)*(k+2)/2)^2               [by Algebra]
            = (1 + ... + k + (k+1))^2         [by Lemma]
     
     Thus we have proven our claim is true by Induction on n
                                                                  QED