CMPU-145, Spring 2013
Alternative version of proof from class
March 27, 2013


    Use induction to show that any postage cost of four or more cents
    can be exactly covered by some combination of 2-cent and 5-cent stamps.

    For example, 23 cents can be covered by four 2-cent stamps and
    three 5-cent stamps.  Note that:  23 = 4*2 + 3*5.

    HINT:  Make your base case n=4.

    HINT:  For the recursive case, consider two sub-cases:

              --  n cents of postage can be covered using only
                  2-cent stamps (i.e., without needing any
                  5-cent stamps)

              --  n cents of postage can be covered, but 
                  requires using at least one 5-cent stamp

  Proof.  Let P(n):  "n = 2*x + 5*y for some natural numbers x and y".

    Note that P(n) says about a particular value n that there exist
    some values x and y that makes n = 2*x + 5*y.  For example, P(23)
    holds since 23 = 2*4 + 5*3 (i.e., x = 4 and y = 3).  Similarly,
    P(24) holds since 24 = 2*12 + 5*0 (i.e., x = 12 and y = 0).  Notice
    that the values of x and y that "work" for one n might be completely
    different from those that work for some other n.

    Base Case.  n=4.  P(4):  "4 = 2x + 5y for some x and y".

      Yes, because 4 = 2*2 + 5*0 (i.e., x = 2, y = 0).

    Rec Case.  Assume P(n) holds:  "n = 2x + 5y for some x and y", n >= 4.

               Prove that P(n+1) holds:  "n+1 = 2x' + 5y' for some x' and y'".

                 (NOTE:  Using x' and y', because they may be different 
                         from x and y.)

      Sub-Case 1:  Suppose y = 0.

        Then n = 2x.  Since n >= 4, we have x >= 2.

        Then n+1 = 2x + 1 

                 = 2(x-2) + 4 + 1, arithmetic

             	 = 2x' + 5y', where x' = x-2 >= 0 (since x >= 2)
                               and y' = 1.

        Thus, n+1 = 2x' + 5y' for some natural numbers x' and y'.

      Sub-Case 2:  Suppose y > 0.

        Then n = 2x + 5y, where y > 0.

        Then n+1 = 2x + 5y + 1, where y > 0

                 = 2x + 5(y-1) + 6, arithmetic

                 = 2(x+3) + 5(y-1), arithmetic

                 = 2x' + 5y', where x' = x+3, and y' = y-1 >= 0 (since y > 0)

        Thus, n+1 = 2x' + 5y' for some natural numbers x' and y'.