Consider the recursion Fk = Fk−1 + Fk−2, k ≥ 2, with F0 = 0 and F1 = 1. Prove

that Fk is even if and only if 3 | k. In other words, prove that, modulo 2, F3t = 0,

F3t+1 = 1, and F3t+2 = 1 for t ≥ 0.

I'm just having some trouble solving the above proof. I see why it works (because odd + odd = even, even + odd = odd, etc), but I cannot prove it with induction.