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

1.  (a) Conjecture:  For all n >= 1, it takes exactly n-1 multiplication
        operations to compute the product of any n numbers, no matter how
        the product is parenthesized (i.e., no matter in what order the
        multiplication operations are performed).

    (b) 0.  Predicate:  Let P(n) be the statement:  It takes exactly n-1
            multiplication operations to compute the product of any n
            numbers, no matter how the product is parenthesized.

        1.  Base Case:  To prove P(1), consider the product of any 1 number
            a_1: this requires no multiplication operations to compute, and
            1-1 = 0.
            Hence, P(1) holds.

        2.  Ind. Hyp.:  Let n >= 1 and suppose P(n), i.e., it takes exactly
            n-1 multiplication operations to compute the product of any n
            numbers, no matter how the product is parenthesized.

        3.  Ind. Step:  To prove P(n+1), consider the product of n+1
            arbitrary numbers a_1 ... a_{n+1}.  Since n >= 1 (by IH),
            n+1 > 1 and it will take at least one multiplication operation
            to compute the product.  Consider the first multiplication
            operation performed: a_i x a_{i+1} for some pair of adjacent
            numbers (1 <= i <= n), and let a'_i = a_i a_{i+1}.  The
            remaining product consists of a_1...a_{i-1} a'_i a_{i+2}...a_n,
            i.e., it consists of n numbers.  By the IH, it will take
            exactly n-1 multiplication operations to compute the rest of
            the product.  Together with the first multiplication operation,
            this gives exactly 1+(n-1) = n = (n+1)-1 operations.  Since we
            considered an arbitrary way to perform the first multiplication
            operation, and all ways to compute the rest of the product,
            P(n+1) holds.

        4.  Conclusion:  By induction, for all n >= 1, P(n), i.e., it takes
            exactly n-1 multiplication operations to compute the product of
            any n numbers, no matter how the product is parenthesized.

    (c) 0.  Predicate:  Let P(n) be the statement:  It takes exactly n-1
            multiplication operations to compute the product of any n
            numbers, no matter how the product is parenthesized.

        1.  Base Case:  To prove P(1), consider the product of any 1 number
            a_1: this requires no multiplication operations to compute, and
            1-1 = 0.
            Hence, P(1) holds.

        2.  Ind. Hyp.:  Let n > 1 [since we've already proved P(1) and we're
            about to try to prove P(n)] and suppose that for all 1 <= k < n,
            P(k), i.e., it takes exactly k-1 multiplication operations to
            compute the product of any k numbers, no matter how the product
            is parenthesized.

        3.  Ind. Step:  To prove P(n), consider the product of n arbitrary
            numbers a_1 ... a_n.  Since n > 1 (by IH), we have to perform
            at least one multiplication operation to compute the product of
            a_1 ... a_n.  Consider the last multiplication operation
            performed: (a_1...a_i) x (a_{i+1}...a_n), for some 1 <= i < n.
            By the IH, it takes i-1 operations to compute the product of
            a_1 ... a_i, and it takes n-i-1 operations to compute the
            product of a_{i+1} ... a_n (since 1 <= i < n -> n-1 >= n-i > 0
            so the IH applies to a_{i+1} ... a_n).  Hence, it takes 1 + i-1
            + n-i-1 = n-1 operations to compute the product a_1 ... a_n.
            Since we considered an arbitrary way to compute the last
            multiplication operation, and all ways to compute the rest of
            the product, P(n) holds.

        4.  Conclusion:  By induction, for all n >= 1, P(n), i.e., it takes
            exactly n-1 multiplication operations to compute the product of
            any n numbers, no matter how the product is parenthesized.