Question

Recall that the Fibonacci numbers are defined by F0 = 0,F1 = 1 and Fn+2 = Fn+1 + Fn for all n ∈N∪{0}.

(1) Make and prove an (if and only if) conjecture about which Fibonacci numbers are multiples of 3.

(2) Make a conjecture about which Fibonacci numbers are multiples of 2020. (You do not need to prove your conjecture.)

How many base cases would a proof by induction of your conjecture require?

Answer 1

A)Base case: F(0)=0F(0)=0, 0 is a multiple of 3.F(4)=3F(4)=3, 3 is a multiple of 3.

Inductive Hypothesis: Assume F(k) is a multiple of 3 for some arbitrary positive integer k that is divisible by 4.

Want to prove: That F(k+4)is a multiple of 3 given the inductive hypothesis.

F(k+4)=F(k+3)+F(k+2)

=F(k+2)+F(k+1)+F(k+1)+F(k)

=F(k+1)+F(k)+F(k+1)+F(k+1)+F(k)

=2F(k)+3F(k+1)F(k+4)=F(k+3)+F(k+2)

=F(k+2)+F(k+1)+F(k+1)+F(k)

=F(k+1)+F(k)+F(k+1)+F(k+1)+F(k)

=2F(k)+3F(k+1)

By our hypothesis, F(k) is a multiple of 3, so 2F(k) must also be a multiple of 3. Furthermore, we know that F(k+1) is some integer, so 3F(k+1) must also be multiple of 3. Hence their sum, F(k+4) must also be a multiple of 3.

B)Conjecture. Let f1,f2,...,fm,...be the sequence of the Fibonacci numbers. For each natural number n, the numbers f1,f3,f5.... Are multiple of 2020.

One base case is required