I thought I had this question down, but while looking over my solution, I think I'm missing a step.
I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$.
I approach this with strong induction. I was able to prove the backward implication by assuming the result holds for all $f_k$ up to $n$, and rewriting $f_{n+1}=8f_{n-4}+5f_{n-5}$. Also, I was able to prove that $f_n$ is divisible by $2$, if and only if $n$ is divisible by $3$ by rewriting $f_{n+1}=2f_{n-1}+f_{n-2}$.
I guess it remains to show that $f_{n+1}$ divisible by $4$ implies that $n$ is even, and thus $n$ will be divisible by $6$, but I just can't figure out how to show this last part. I've messed with proofs by contradiction, the contrapositive, but have come up with nothing. How would one do that?