Homework Exercise 2

Due: by 10am on Thu 24 Jan
Worth: 1.5%

For each question, please write your answer formally following the detailed format given in lecture (in particular, define P(n) carefully in your inductive proofs). Keep in mind that approximately half of the marks for each question will be given purely for having the correct proof structure, written up clearly and precisely, irrespective of the correctness of the proof. Also, make sure that you use notation and terminology correctly, and that you explain and justify what you are doing — marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. When computing the product of n distinct real numbers a1a2...an, there are many ways to order the multiplication operations that have to be performed. For example, the product of a1...a5 could be computed in the order (a1a2)(a3(a4a5)), or in the order a1((a2(a3a4))a5), or in many other ways.

    1. Make a conjecture about the number of multiplication operations required to compute the product a1...an of n distinct real numbers, for any n ∈ N — in particular, does this number depend on the order of the operations? For example, it takes four multiplication operations to compute the product (a1a2)(a3(a4a5)): first a4 × a5, then a3 × (a4a5), then a1 × a2, and finally (a1a2) × (a3(a4a5)).

    2. Prove your conjecture using simple induction, by considering each possible way that the first multiplication operation can be performed when computing the product.

    3. Prove your conjecture using complete induction, by considering each possible way that the last multiplication operation can be performed when computing the product.
      For full marks, the inductive step in your proof by complete induction must be significantly different from the inductive step in your proof by simple induction, i.e., the point of this part is to get you to think of a different way of proving your conjecture, not to repeat your simple induction proof within a complete induction structure. (Hint: Look at the last example from last week's lectures.)