Solve the following questions:
1. Consider the Fibonacci sequence f1, f2, f3,...., where f1 = f2 = 1 and fk = fk-1 + fk-2 for k >=3. Use induction to prove that for every integer n >=1,
i=1∑n fi2 = fnfn+1
2. Use mathematical induction to prove that 7|(8n - 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 20, 21, 22, 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 write 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.