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?
Best Answer
One way to look at it is to consider the sequence in $\mathbb{Z}/4\mathbb{Z}$. Same definition: $f_1=f_2=1$ and $f_{n+1}=f_{n}+f_{n-1}$. The sequence hence starts as follows: 1, 1, 2, 3, 1, 0, 1, 1, ... Clearly the sequence is periodic of period 6. You can probably find a way to write this hand-wavy argument more rigorously.