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.