How to prove that a Fibonacci number F(n) is even if and only if n is divisible by 3? So far, I tried proving that F(n) is even if 3 divides n. My steps so far are:
Consider:
F(1) ≡ 1(mod 2)
F(2) ≡ 1(mod 2)
F(3) ≡ 0(mod 2)
F(4) ≡ 1(mod 2)
F(5) ≡ 1(mod 2)
F(6) ≡ 0(mod 2)

Assume there exists a natural number k such that 3 divides k and F(k) is even. Let k = 3. Then k+3 = 6. So F(6) = F(5) + F(4) ≡ 1(mod 2) + 1(mod 2) = 0(mod 2).
Therefore k+3 is even.
How do I go about proving the other way on the biconditional?
 A: You have proved that the Fibonacci sequence is strictly periodic modulo $2$ with period $3$(in other words, $F_{n+3} \equiv F_n \mod 2$ so if $n\equiv 1 \mod 3$ then $F_n \equiv F_1 \mod 2$, if $n\equiv 2 \mod 3,$ then $F_n \equiv F_2 \mod 2$, and if $n \equiv 0 \mod 3$ then $F_n \equiv F_3 \mod 2$.  So, you are done.
A: Induction.  It's true for $1,2,3$ and $F_1 = 1; F_2 = 1; F_3 = 2$
Assume it is true for $3n -2, 3n-1, 3n$ then $F_{3n+1} = F_{3n} + F_{3n-1} = even + odd = odd; F_{3n+2} = F_{3n+1} + F_{3n} = odd + even = odd; F_{3n+3} = F_{3n+2} + F_{3n+1} = odd + odd = even$.  
So it's true for $3n+1, 3n+2, 3n+3$.
That's all.
A: You have the right idea, but you're only computing $F(n)$ for small $n$. Just put the same idea in the general context:
By induction prove that
$F(n)$ is even iff $n$ is divisible by $3$:
The statement is true up to $n=3$ since the sequence starts with $1,1,2$.
 Assume that we have proved it up to $n-1$ with $n-1$ being divisible by $3$. 
So mod 2 the values up until the $(n-1)th$ Fibonacci number are
$..,1,1,0$. 
Then $F(n) \equiv 1+0 \equiv 1$ mod 2,
$..,1,1,0,1$,
so $F(n+1) \equiv 0+1 \equiv 1$,
$..,1,1,0,1,1$
and $F(n+2)\equiv 1+1 \equiv 0$:
$..,1,1,0,1,1,0$
and the statement is proven for $n,n+1$ and $n+2$. 
Since $n+2 = (n-1)+3$ is again divisible by $3$, we have completed the inductive step. 
