Thank you Andrei Lazanu, age 14, School No. 205, Bucharest, Romania for this solution.

First I wrote the Fibonacci numbers up to

f_{12}

, as calculated from the recurrence relation in the problem. Here they are:

\begin{matrix} f_{0} & = 0, f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, f_{6} = 8, \\ f_{7} & = 13, f_{8} = 21, f_{9} = 34, f_{10} = 55, f_{11} = 89, f_{12} = 144 \end{matrix} .

I observed that

f_{3}, f_{6}, f_{9}

and

f_{12}

are even. Up to here,

f_{n}

is even when

n

is a multiple of 3. I must prove that such a pattern continues.

I also observed that

f_{4}, f_{8}

and

f_{12}

are multiples of 3. I could deduce that

f_{n}

is a multiple of 3 when

n

is a multiple of 4.

Now, I must prove the conjectures that I observed. I shall prove them both by induction.

1)

f_{n}

- even

f_{3} = 2

as calculated before. Let

p

be a positive integer. I consider that

f_{3 p}

is even. I must prove that

f_{3 p + 3}

is also even. From the definition of the Fibonacci Sequence, I obtain:

f_{3 p + 3} = f_{3 p + 2} + f_{3 p + 1} = (f_{3 p + 1} + f_{3 p}) + f_{3 p + 1} = 2 f_{3 p + 1} + f_{3 p} .

Here,

2 f_{3 p + 1}

is divisible by 2, and, from my hypothesis,

f_{3 p}

is also divisible by 2. So,

f_{3 p + 3}

is divisible by 2.

Hence, by the axiom of induction,

f_{n}

is even if

n

is a multiple of 3.

2)

f_{n}

- multiple of 3

Let

q

be a positive integer. I consider that

f_{4 q}

is a multiple of 3. I shall prove now that

f_{4 q + 4}

is a multiple of 3:

\begin{matrix} f_{4 q + 4} & = f_{4 q + 3} + f_{4 q + 2} = (f_{4 q + 2} + f_{4 q + 1}) + f_{4 q + 2} = 2 f_{4 q + 2} + f_{4 q + 1} \\ = 2 (f_{4 q + 1} + f_{4 q}) + f_{4 q + 1} = 3 f_{4 q + 1} + f_{4 q} . \end{matrix}

In this case

3 f_{4 q + 1}

is divisible by 3, and so is

f_{4 q}

(from my hypothesis). I must also say that

f_{4} = 3

, which is a multiple of 3. Hence by the axiom of induction

f_{n}

is a multiple of 3 if

n

is a multiple of 4.

Editor's note: We should still show that these are the only Fibonnaci numbers divisible by 3 to prove the 'only if' condition.

If any two consecutive Fibonnaci numbers have a common factor (say 3) then every Fibonnaci number must have that factor. This is clearly not the case so no two consecutive Fibonnaci numbers can have a common factor. If

f_{n}

and

f_{n + 2}

are both multiples of 3 then

f_{n + 1}

must also be a multiple of 3 and hence all Fibonnaci numbers will be multiples of 3 which is not the case. This shows that if

f_{n}

and

f_{n + 4}

are multiples of 3 then no Fibonnaci numbers between them can be multiples of 3, that is

f_{n}

is divisible by 3 only if

n

is a multiple of 4.