Solve the following problems:
1. Consider the Fibonacci sequence f1, f2, f3,...., where f1 = f2 = 1 and fk = f_{k-1} + f_{k-2} for k >=3. Use induction to prove that for every integer n >=1,
_{i=1}∑^{n} f_{i}^{2} = f_{n}f_{n+1}
2. Use mathematical induction to prove that 7|(8^{n} - 1) for all positive integers n.
3. Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2^{0}, 2^{1}, 2^{2}, etc. Hint: For the induction step, separately consider the cases where k +1 is even and where it is odd. When it
is even, note that (k + 1)/2 is an integer.
4. What is wrong with the following "proof" by strong induction?
"Theorem": For every nonnegative integer n, 5n = 0.
"Proof":
Basis: For n = 0, 5.n = 5 .0 = 0. So the statement holds for n = 0.
Induction Hypothesis: Assume that 5n = 0 for all nonnegative integers n = 0, 1,.....,k.
Induction Step: Consider n = k + 1. We can prepare k + 1 = i + j, where i and j are natural numbers less than k + 1.
By the induction hypothesis, 5(k + 1) = 5(i + j) = 5i + 5j = 0 + 0 = 0.