Prove that the following holds: $3|F_n$ if and only if $4|n$
Base case for $n=1$:
$F_1$=1, so $F_1$ is not divisible by 3 and 1 is not divisble by 4.
So the proposition holds for $k=1$
Continue for n=2, n=3 and n=4.
Assume $3|F(4k)$. We now have to prove that the proposition also holds for $4(k+1)=4k+4$.
$5F(4k)$ is divisible by 3 by our hypothesis and it is obvious that $3F(4k-1)$ is divisible by 3.
$3F(4k)$ is divisble by 3 by our hypothesis and since $n$ already is a multiple of 4 $(n-1)$ can't possibly be a multiple of 4 to. So by our hypothesis $2F(4k-1)$ is not divisible by 3 and thus $F(4k+3)$ is not divisible by 3.
I continue the proof for $F(4k+2)$ and $F(4k+1)$ and conclude that by induction $3|F_n$ holds if $4|n$ holds, but the proposition involves a bi-implication, so I need to prove that $4|n$ holds if $3|F_n$ holds. However, I don't know where to begin.
I also think my proof is too lengthy. So I would like to know if there is a simpler, more elegant way to prove the proposition (induction is not required).