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


1.  I will show more than two different structures for each part -- any two
    of them would be suitable, as well as variations thereof.

    (a) For all odd integers n >= 3, P(n).

        1.  Predicate:  P(n).
            Base Case:  Prove P(3).
            Ind. Hyp.:  Suppose n >= 3 and n is odd and P(n).
            Ind. Step:  Prove P(n+2).
            Conclusion:  \-/ odd n >= 3, P(n).

        2.  Predicate:  Q(n) = P(2n+1).
            Base Case:  Prove Q(1) (same as P(3)).
            Ind. Hyp.:  Suppose n >= 1 and Q(n) (same as P(2n+1)).
            Ind. Step:  Prove Q(n+1) (same as P(2n+3)).
            Conclusion:  \-/ n >= 1, Q(n), i.e.,
                \-/ odd n >= 3, P(n).

        3.  Predicate:  Q(n) = n is odd /\ n >= 3 -> P(n).
            Ind. Hyp.:  Suppose n (- N and \-/ k < n, Q(k).
            Ind. Step:  To prove Q(n), suppose n is odd and n >= 3.
                Case 1:  n = 3:  Prove P(3).
                Case 2:  n > 3:  Then n >= 5 so n-2 >= 3 and n-2 is odd.
                    By the IH, Q(n-2), which implies P(n-2).
                    Use this to prove P(n).
            Conclusion:  \-/ n, Q(n), i.e.,
                \-/ odd n >= 3, P(n).

    (b) For all n that are positive multiples of 3, P(n).

        1.  Predicate:  P(n).
            Base Case:  Prove P(3).
            Ind. Hyp.:  Suppose n >= 3 is a multiple of 3 and P(n).
            Ind. Step:  Prove P(n+3).
            Conclusion:  \-/ n >= 3, n multiple of 3, P(n).

        2.  Predicate:  Q(n) = P(3n).
            Base Case:  Prove Q(1) (same as P(3)).
            Ind. Hyp.:  Suppose n >= 1 and Q(n) (same as P(3n)).
            Ind. Step:  Prove Q(n+1) (same as P(3n+3)).
            Conclusion:  \-/ n >= 1, Q(n), i.e.,
                \-/ n >= 1, P(3n).

        3.  Predicate:  Q(n) = -] k > 0, n = 3k -> P(n).
            Ind. Hyp.:  Suppose n (- N and \-/ m < n, Q(m).
            Ind. Step:  To prove Q(n), suppose -] k > 0, n = 3k.
                Case 1:  k = 1, i.e., n = 3:  Prove P(3).
                Case 2:  k > 1, i.e., n > 3:  Then n-3 = 3(k-1).
                    By the IH, Q(n-3), which implies P(n-3).
                    Use this to prove P(n).
            Conclusion:  \-/ n, Q(n), i.e.,
                \-/ n that are positive multiples of 3, P(n).

    (c) For all n that are powers of 2 (i.e., n = 2^k for some k (- N),
        P(n).

        1.  Predicate:  P(n).
            Base Case:  Prove P(1).
            Ind. Hyp.:  Suppose n >= 1 is a power of 2 and P(n).
            Ind. Step:  Prove P(2n).
            Conclusion:  \-/ n that are powers of 2, P(n).

        2.  Predicate:  Q(n) = P(2^n).
            Base Case:  Prove Q(0) (same as P(1)).
            Ind. Hyp.:  Suppose n (- N and Q(n) (same as P(2^n)).
            Ind. Step:  Prove Q(n+1) (same as P(2^{n+1})).
            Conclusion:  \-/ n, Q(n), i.e.,
                \-/ n that are powers of 2, P(n).

        3.  Predicate:  Q(n) = -] k, n = 2^k -> P(n).
            Ind. Hyp.:  Suppose n (- N and \-/ m < n, Q(m).
            Ind. Step:  To prove Q(n), suppose -] k, n = 2^k.
                Case 1:  k = 0:  Prove P(1).
                Case 2:  k > 0:  Then n > 1 and n/2 = 2^{k-1}.
                    By the IH, Q(n/2), which implies P(n/2).
                    Use this to prove P(n).
            Conclusion:  \-/ n, Q(n), i.e.,
                \-/ n that are powers of 2, P(n).


2.  Conjecture:  For all k (- N, for all n (- {0,1,...,2^k}, it is possible
        to achieve value (n,2^k-n) or (2^k-n,n) starting from (0,2^k).

    Predicate:  Let R(k,n) = "there is a sequence of moves from (0,2^k) to
        (n,2^k-n) or (2^k-n,n)" and P(k) = "\-/ n (- {0,...,2^k}, R(k,n)".

    Base case:  P(0) = "\-/ n (- {0,1}, there is a sequence of moves from
        (0,1) to (n,1-n) or (1-n,n)", which is trivially true for n = 0
        and for n = 1 (no move required).

    Ind. Hyp.:  Suppose k (- N and P(k), i.e., \-/ n (- {0,1,...,2^k},
        there is a sequence of moves from (0,2^k) to (n,2^k-n) or
        (2^k-n,n).

    Ind. Step:  To prove P(k+1), suppose n (- {0,1,...,2^{k+1}}.
        We must show R(k+1,n).  Either n is even or n is odd.
        Case 1:  n is even.  Since 0 <= n <= 2^{k+1}, 0 <= n/2 <= 2^k so by
            the I.H., R(k,n/2).  The same sequence of moves starting from
            (0,2^{k+1}) will yield (n,2^{k+1}-n) or (2^{k+1}-n,n), i.e.,
            R(k+1,n) -- see Lemma below.
        Case 2:  n is odd.  Either n < 2^k or n > 2^k.
            Subcase A:  n < 2^k.  By the IH, R(k,n) and the same sequence
                of moves that takes (0,2^k) to (n,2^k-n) or (2^k-n,n) will
                take (0,2^{k+1}) to (2n,2^{k+1}-2n) or (2^{k+1}-2n,2n).
                One last move then yields (n,2^{k+1}-n) or (2^{k+1}-n,n),
                i.e., R(k+1,n).
            Subcase B:  n > 2^k.  Let m = 2^{k+1}-n.  Then m < 2^k and as
                in Subcase A, R(k+1,m), i.e., there is a sequence of moves
                starting form (0,2^{k+1}) end ending with (m,2^{k+1}-m) or
                (2^{k+1}-m,m); however, (m,2^{k+1}-m) = (2^{k+1}-n,n) and
                (2^{k+1}-m,m) = (n,2^{k+1}-n), so R(k+1,n).
            In each subcase, R(k+1,n).
        In each case, R(k+1,n).

    Conclusion:  \-/ k, \-/ n (- {0,1,...,2^k}, R(k,n), i.e., it is always
        possible to win the game for all values of k,n such that n <= 2^k.

    Lemma:  \-/ k, \-/ n (- {0,1,...,2^k}, any play of the game starting
        from (0,2^k) and ending in (n,2^k-n) can be converted to a play of
        the game starting from (0,2^{k+1}) and ending in (2n,2^{k+1}-2n),
        by following the same sequence of moves.  This can be proved
        formally by induction, using the fact that each individual move
        (a,b) => (a/2,b+a/2) becomes (2a,2b) => (a,2b-a).

3.  Predicate:  P(n) = "every full binary tree with n nodes contains
        exactly (n + 1) / 2 leaves".

    Base case:  To prove P(1), let T be a full binary tree with 1 node.
        Then T consists of a single leaf, and (1 + 1) / 2 = 1, i.e., P(1)
        holds.

    Ind. Hyp.:  Suppose n > 1 and \-/ k (- {1,...,n-1}, P(k), i.e., every
        full binary tree with 1 <= k < n nodes contains exactly (k + 1) / 2
        leaves.

    Ind. Step:  To prove P(n), let T be a full binary tree with n nodes.
        Since n > 1, the root of T has two children.  Let L and R be the
        subtrees rooted at the left and right child of T, respectively, and
        let i be the number of nodes in L, j be the number of nodes in R.
        Then, n = 1 + i + j, and since i >= 1 and j >= 1 (both subtrees are
        non-empty), we have that 1 <= i < n, 1 <= j < n.
        By the IH, L contains exactly (i + 1) / 2 leaves and R contains
        exactly (j + 1) / 2 leaves, which means T contains exactly
        (i + 1) / 2 + (j + 1) / 2 = (i + j + 1 + 1) / 2 = (n + 1) / 2
        leaves.

    Conclusion:  \-/ n >= 1, P(n), i.e., every full binary tree with n
        nodes contains exaclty (n + 1) / 2 leaves.

    Alternate proof by modified simple induction -- it was not necessary to
    give both proofs, I do this in the sample solutions only to show the
    possibility:

    Predicate:  P(n) = "every full binary tree with n nodes contains
        exactly (n + 1) / 2 leaves".

    Base case:  To prove P(1), let T be a full binary tree with 1 node.
        Then T consists of a single leaf, and (1 + 1) / 2 = 1, i.e., P(1)
        holds.

    Ind. Hyp.:  Suppose n >= 1 and P(n), i.e., every full binary tree with
        n nodes contains exactly (n + 1) / 2 leaves.

    Ind. Step:  To prove P(n+2), let T be a full binary tree with n+2
        nodes.  Since n >= 1, n+2 >= 3 so T contains at least one internal
        node (a node with two children).  Then, T must contain at least one
        internal node both of whose children are leaves -- if every
        internal node's children were also internal nodes, the tree would
        be infinite!  Let C be such a node, and let T' be the tree obtained
        from T by removing both of C's children (turning C into a leaf).
        T' contains n nodes so by the IH, T' contains exactly (n + 1) / 2
        leaves.  But then, T contains exactly (n + 1) / 2 - 1 + 2 leaves
        (-1 because C is not a leaf in T, +2 because both of C's children
        are leaves in T), and (n + 1) / 2 - 1 + 2 = (n+2 + 1) / 2, as
        desired.

    Conclusion:  \-/ n >= 1, P(n), i.e., every full binary tree with n
        nodes contains exaclty (n + 1) / 2 leaves.