# How to prove that every third Fibonacci number is even?

1. Mar 21, 2017

### Eclair_de_XII

1. The problem statement, all variables and given/known data
"Consider the sequence $F_1$, $F_2$, $F_3$, . . . , where
$F_1 = 1$, $F_2 = 1$, $F_3 = 2$, $F_4 = 3$, $F_5 = 5$ and $F_6 = 8$.
The terms of this sequence are called Fibonacci numbers.
(a) Define the sequence of Fibonacci numbers by means of a recurrence relation.
(b) Prove that $2 | F_n$ if and only if $3 | n$.

2. Relevant equations
(a) $F_n=F_{n-2}+F_{n-1}$

3. The attempt at a solution
(b)
Basically, I'm going to express every Fibonacci number in terms of $mod2$ and express $n$ as $n=3x$ for some $x∈ℕ$.

For $x=1$, $F_3=F_1+F_2=1mod2+1mod2=0mod2$.
Then assuming that $F_{3k}=0mod2$ for some $k>1$, I need to prove that $F_{3(k+1)}=F_{3k+1}+F_{3k+2}$.

So I have $F_{3k+1}=0mod2+1mod2$ and $F_{3k+2}=0mod2+1mod2$.
Adding them up gives $F_{3(k+1)}=F_{3k+1}+F_{3k+2}=0mod2+1mod2+0mod2+1mod2=0mod2$.

And I'm pretty sure this isn't sufficient to complete the inductive proof. Can anyone check my work? Thanks.

2. Mar 21, 2017

### PeroK

You we're supposed to show iff.

The proof would be simpler if you considered the sequence in sets of 3 and explicitly showed that, modulo 2, the sequence is:

$1, 1, 0,1,1,0 \dots$