Answers to HW #3

1. Let f(n) be a function from N -> N (the naturals), satisfying f(0) = 0 and for n>0, f(n) = 2 * f(n-1) + 1.
Prove that for all n in the naturals, f(n) = 2ⁿ - 1.

A. The proof is by induction on n.
The base case is n=0, which is given to us.
Now assume n>0. Then
f(n) = 2 f(n-1) + 1
= 2 (2^n-1 - 1) + 1 by induction
= 2ⁿ - 2 + 1
= 2ⁿ - 1, as we wanted to show.

2. Prove that for all n at least 2 (this induction doesn't start from 0, or from 1!),
that the product of the numbers {1 - 1/i : i = 2,...,n} is 1/n.

(I guess you can start from 1 if you want, regarding the LHS as an empty product, so = 1. But the problem doesn't ask you to think about that.)

A.
For n=2, the statement is that 1 - 1/2 = 1/2, which is true.
Now assume n>2.
Then product_i=2ⁿ (1 - 1/i) = (1 - 1/n) product_i=2^n-1 (1 - 1/i)
= (1 - 1/n) 1/(n-1) by induction
= 1/n, as was to be shown.

3. Let f:N->N satisfy
f(0) = 38
f(1) = 39
for all n at least 2, f(n) = 3f(n-1) - 2f(n-2).
Prove that for all n in N, f(n) = 2ⁿ + 37.

A. The formula is easy to check for n=0,1.
Now assume n is at least 2.
Then f(n) = 3 f(n-1) - 2 f(n-2)
= 3 (2^n-1 + 37) - 2 (2^n-2 + 37) by (strong) induction; each of n-1, n-2 are < n
= (3-1) 2^n-1 + 37
= 2ⁿ + 37 as was to be shown.