CMPU-145, Spring 2013
Asmt. 4 Solutions

  1.  Recall the definition of the addition function, seen in class:

        (1) x +  0 = x            
        (2) x + Sy = S(x + y)

      Recall that we proved in class the following theorems:

        (GEORGE)  0 + x = x  for all natural numbers x.

        (CRACKIE) x + Sy = Sx + y for all natural numbers x and y.

      Feel free to use these results in what follows.

      Prove the following:  x + y = y + x for all natural numbers x and y.

      Your proof should only use rules 1 and 2 above, as well as 
      GEORGE and CRACKIE.

      For full credit, you must clearly specify the proposition that
      you are using; and the structure of your inductive proof (i.e.,
      base case and recursive case) must be clear.

      Proof.  P(x):  x + y = y + x for all natural numbers y.

        Base Case, P(0):  x + 0 = 0 + x.

           LHS = x + 0 
               = x,         by (1)
               = 0 + x,     by George
               = RHS

        Recursive Case:  Assume P(k):  k + y = y + k for all y.

          Prove P(Sk):  Sk + y = y + Sk for all y.

            LHS = Sk + y
                = k + Sy,   by Crackie
                = S(k+y),   by (2)
                = S(y+k),   by P(k)
                = y + Sk,   by (2)
                = RHS


  2.  Given the following definition of a multiplication function:
 
        (3)    x *  0 = 0
        (4)    x * Sy = (x*y) + x

      Prove that (x+y)*z = x*z + y*z  for all natural numbers x, y and z.

    PROOF.  Let P(z) be the proposition:  (x+y)*z = x*z  for all x and y.

      Base Case, P(0):  (x+y)*0 = x*0 + y*0

        LHS = (x+y)*0 = 0, by 3
            = 0 + 0,       by 1
            = x*0 + y*0,   by 3
            = RHS

      Recursive Case:  Assume P(k):  (x+y)*k = x*k + y*k

        Prove P(Sk):  (x+y)*Sk = x*Sk + y*Sk

          LHS = (x+y)*Sk
              = (x+y)*k + (x+y),       by 4
              = (x*k + y*k) + (x+y),   by P(k)
              = (x*k + x) + (y*k + y), by assoc & commut props of addn
              = x*Sk + y*Sk,           by 4
              = RHS