Fibonacci clarification

Question

As explained in Excursion 4.5, the Fibonacci numbers are defined by the rules: F(0) = 0, F(1) = 1, and for all n with n ≥ 2, F(n) = F(n-1) + F(n-2). Which of these claims about the Fibonacci numbers is false? Select one:

a. For every n with n ≥ 5, F(n) ≥ 2n/2.

b. For every natural n, F(n) is divisible by 3 if and only if n is divisible by 4.

c. For every n, F(n) ≤ 2n.

d. The sum for i from 0 through n of F(i) is F(n+2) - 1.

This was a question on a test that I got wrong. My answer was b. I am looking to understand how this is possible. My understanding is that F(n) is a fibonacci number. If so, not all numbers are divisible by 3 and are also divisible by 4.

You can prove b. using induction, or just look at the residues one obtains when dividing F(n) by 3:
$0, 1, 1, 2, 0, 2, 2, 1, 0, \dots$ — bakula, Oct 23 '15 at 15:33
It's supposed to. But there have been questions before where later was given credit for being correct as well. Do it's possible that there are — user_123945839432, Oct 23 '15 at 15:36
For b, note that in mod $3$, we have $\color{red}{0},\color{red}{1},1,2,0,2,2,1,\color{red}{0},\color{red}{1},1,...$ — mathlove, Oct 23 '15 at 15:37
Doe $(a)$ really say $2n/2$? Or something else? Because $2n/2$ is sill. — Thomas Andrews, Oct 23 '15 at 15:39

score 1 · Accepted Answer · answered Oct 23 '15 at 15:34

If so, not all numbers are divisible by 3 and are also divisible by 4.

The statement doesn't say that. The statement says that if $F(n)$ is divisible by $3$, then $n$ is divisible by $4$, and vice versa.

To see that this statement is true, I advise you to think about the fact that $$F(n+1)\equiv F(n) + F(n-1)\mod 3$$

and then look at the whole sequence modulo $3$. You might notice a pattern.

Fibonacci clarification

1 Answers1