As a start it helps to convert the Fibonacci sequence into a
sequence of remainders.
The remainders on division by 2 are : 1, 1, 0, 1, 1, 0, 1, 1
The remainders on division by 3 are : 1, 1, 2, 0, 2, 2, 1, 0, 1, 1,
2, 0
Each term is produced by adding together the two preceding terms,
and keeping in mind that these are remainders after division.
So once a pair of consecutive terms appear a second time the
sequence must repeat from then on.
The multiples of 2 (or 3) in the original occur where the term is
zero in the remainders sequence.
Thank you Andrei from School No. 205 in Bucharest, Romania for
taking this further with a more algebraic solution.
First I wrote the Fibonacci numbers up to $f_{12}$, as calculated
from the recurrence relation in the problem. Here they are:
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_{3p}$ is even. I must prove that $f_{3p+3}$ is
also even. From the definition of the Fibonacci Sequence, I obtain:
Here, $2f_{3p+1}$ is divisible by 2, and, from my hypothesis,
$f_{3p}$ is also divisible by 2. So, $f_{3p+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_{4q}$ is a
multiple of 3. I shall prove now that $f_{4q+4}$ is a multiple of
3:
In this case $3f_{4q+1}$ is divisible by 3, and so is $f_{4q}$
(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 Fibonacci numbers have a common factor (say
3) then every Fibonacci number must have that factor. This is
clearly not the case so no two consecutive Fibonacci 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
Fibonacci 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
Fibonacci numbers between them can be multiples of 3, that is $f_n$
is divisible by 3 only if $n$ is a multiple of 4.