HW #3 due Monday May 5 (yes, Monday)

More practicing proofs by induction.

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

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.)

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.

Book:
11.6, 11.10, 11.15.
Think hard about 11.7 but don't turn anything in about it.