Date: Mon, 01 Mar 2004 16:20:43 -0600 (CST)
   From: Mark Jacobson <jacobson@math-cs.cns.uni.edu>
     To: 810-080-01@uni.edu, 810-080-02@uni.edu
Subject: 2nd principle of mathematical induction proof style...

discrete students,

     Prove that any amount of postage >= 64 cents can be built
     using only 5 cent and 17 cent stamps.

     This was proven in class and you can see the web page and/or
                            your handout for the solution.

     http://www.cns.uni.edu/~jacobson/hw080p111e64.gif

     Another approach to proving this would be as follows:
     (Uses SECOND PRINCIPLE OF INDUCTION)
           -----------------------------

     BASIS step:  Prove it for 64 cents, up to 64 + 5 = 69 cents.


                postage    a   b    5 cent total  17 cent total
                  64       6   2        30           34
                  65      13   0        65            0
                  66       3   3        15           51
                  67      10   1        50           17
                  68       0   4         0           68
                  69       7   2        35           34

     Inductive Step:
                 Assume that we can make r cents postage,
                 where 64 =< r <= k.  This is our IH Inductive Hypothesis.

                 Need to show that k+1 cents postage can be made.

                 We can assume that k+1 > 69, since we have shown
                                              that postage can
                                              be made all the way
                                              up to and including
                                              69 cents.

                 Take away a 5 cent stamp from the k+1 cents postage.

                 So k+1 - 5 = k - 4

                 We gave k - 4 cents postage.  Since k - 4 is at
                                               least 69 - 4 or 65 cents,
                                               that amount of
                                               postage works okay.

             Notice this is NOT the previous domino (rung of the ladder),
             but is 5 rungs back from k + 1, but that is okay.

             The 2nd priciple of math induction states that
             P(k) is P(64), ..., P(r), .... P(k) all work okay,
             that is everything up to the previous rung of the
             ladder, not JUST the previous rung.
                     --- ----

             Since k - 4 cents is within that range, all we have
             to do is purchase a 5 cent stamp:

             k - 4 cents
           +     5 cents
            ------------
            k + 1 cents postage   SHOWN (PROVEN)

            Look at Example 24 on page 104 of the textbook.
            You do NOT need to use the 2nd principle of math induction,
            and some semesters I do not even ever mention it.

            To me, the proof by using the first principle is much
            clearer and more convincing.

      Study the web page for binary relations and r, s, t, a and i
      properties of binary relations before the Wednesday class.

      http://www.cns.uni.edu/~jacobson/c080.html

            Mark