Homework Exercise 2 — Sample Solutions
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).
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.
Base Case:
To prove P(1),
consider the product of any 1 number a1:
this requires no multiplication operations to compute, and
1-1 = 0.
Hence, P(1) holds.
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.
Ind. Step:
To prove P(n+1),
consider the product of n+1 arbitrary numbers
a1 ... an+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:
ai × ai+1
for some pair of adjacent numbers
(1 ≤ i ≤ n),
and let a'i =
ai ai+1.
The remaining product consists of
a1...ai-1
a'i
ai+2...an, 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.
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.
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.
Base Case:
To prove P(1),
consider the product of any 1 number a1:
this requires no multiplication operations to compute, and
1-1 = 0.
Hence, P(1) holds.
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.
Ind. Step:
To prove P(n), consider the product of
n arbitrary numbers
a1 ... an.
Since n > 1 (by IH),
we have to perform at least one multiplication operation
to compute the product of
a1 ... an.
Consider the last multiplication operation performed:
(a1...ai) ×
(ai+1...an),
for some 1 ≤ i < n.
By the IH, it takes i-1 operations to compute the product of
a1 ... ai,
and it takes n-i-1 operations to compute the product of
ai+1 ... an
(since 1 ≤ i < n →
n-1 ≥ n-i > 0
so the IH applies to
ai+1 ... an).
Hence, it takes
1 + i-1 + n-i-1
= n-1 operations to compute the product
a1 ... an.
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.
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.
|
![[FP]](../images/fp.png){kind=small}
