Unit 17 Answers
1. The sum for small values of n are starting
with n = 1,
1/2, 3/4, 7/8, 15/16, ... .
Hence for general n the sum is guessed
to be
( 2n - 1 )/2n.
A proof for that is as follows:
Let P(n) be the statement " 1/2 + 1/4 + ... + 1/2n = ( 2n - 1 )/2n. "
Basis step: When n = 1, the left hand side is 1/2 and the right hand side is also 1/2. Hence P(1) is true.
Inductive step: Assume that P(n) is true.
Then 1/2 + 1/4 + ... + 1/2n + 1/2n+1
= ( 2n - 1 )/2n + 1/2n+1
= ( 2*2n - 2 + 1 )/2n+1
= ( 2n+1 - 1 )/2n+1
Hence P(n+1) holds.
2. Let P(n) be the statement " to compute the product of n numbers, n - 1 multiplications are necessary."
Assume that P(i) is true for all i, i < n. We are going to prove that P(n) is true.
Consider the last multiplication used to compute the product of n numbers.
Then it multiplies two products. Let b1b2...bi
and bi+1bi+2...bn be those two products,
where each bj is equal to some ak. That is,
the last multiplication computes the product of b1b2...bi
and bi+1bi+2...bn, and the result is
the product of n ai's.
Then by the induction hypothesis b1b2...bi
needs i - 1 multiplications to compute it,
and bi+1bi+2...bn needs
n - i - 1 multiplications to compute it. Thus the product
b1b2...bi
bi+1bi+2...bn
is computed with (i - 1) + (n - i - 1)+ 1
= n - 1 multiplications.
Hence P(n) is true.