Explaining mathematical and strong induction


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=1n  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.

Request for Solution File

Ask an Expert for Answer!!
Mathematics: Explaining mathematical and strong induction
Reference No:- TGS01781

Expected delivery within 24 Hours