===========================================================================
CSC 236           Homework Exercise 1 -- Sample Solutions       Winter 2008
===========================================================================


1.  Conjecture:  For all n (- N, \sum_{i=0,1,...,n} 2^{i+1} = 2^{n+2} - 2.

    Proof by induction:

     -  Statement:  Let P(n) be the statement:
            \sum_{i=0,1,...,n} 2^{i+1} = 2^{n+2} - 2.
     -  Base Case:  \sum_{i=0,...,0} 2^{i+1} = 2^1 = 4 - 2 = 2^{0+2} - 2,
            so P(0) holds.
     -  Ind. Hyp.:  Let n (- N and suppose P(n) holds, i.e.,
            \sum_{i=0,1,...,n} 2^{i+1} = 2^{n+2} - 2.
     -  Ind. Step:  \sum_{i=0,1,...,n+1} 2^{i+1}
                  = (\sum_{i=0,1,...,n} 2^{i+1}) + 2^{n+2}
                  = (2^{n+2} - 2) + 2^{n+2}  (by the ind. hyp.)
                  = 2 x 2^{n+2} - 2
                  = 2^{n+3} - 2,
            so P(n+1) holds.
     -  Conclusion:  By induction, \-/ n (- N,
            \sum_{i=0,1,...,n} 2^{i+1} = 2^{n+2} - 2.


2.  Conjecture:  It is possible to make every amount of postage of 14c or
    more using only 3c and 8c stamps.

    Proof by induction:

     -  Statement:  Let P(n) be the statement: -] t (- N, -] e (- N,
            n = 3t + 8e.
     -  Base Case:  14 = 6 + 8 = 3(2) + 8(1), so P(14) holds (by picking
            t=2, e=1).
     -  Ind. Hyp.:  Let n >= 14 and suppose P(n) holds, i.e.,
            -] t (- N, -] e (- N, n = 3t + 8e.
     -  Ind. Step:  To prove P(n+1), consider two cases for the value of e
            that we know to exist from the ind. hyp.
             .  Case 1:  If e = 0, then n+1 = 3t + 8(0) + 1 so 3t = n >= 14
                    and t >= 5.  Then, n+1 = 3t + 1 = 3t - 15 + 15 + 1
                      = 3(t-5) + 16 = 3(t-5) + 8(2), so P(n+1) holds (by
                    picking t'=t-5, e'=2, where we know t' (- N because
                    t >= 5).
             .  Case 2:  If e > 0, then n+1 = 3t + 8e + 1 = 3t + 8(e-1) + 9
                      = 3(t+3) + 8(e-1), so P(n+1) holds (by picking
                    t'=t+3, e'=e-1, where we know e' (- N because e >= 1).
            In either case, P(n+1) holds.
     -  Conclusion:  By induction, \-/ n >= 14, P(n), i.e..  it is possible
            to make every amount of postage of 14c or more using only 3c
            and 8c stamps.