Consider the recursion $F_k = F_{k-1} + F_{k-2},$ $ k\geq 2,$ $F_0 = 0$ and $F_1 = 1$, then show that $F_k$ is even iff $3|k$
I tried to do a proof by induction:
The statement is true for base cases $F_0$ to $F_3$, simply by plugging in values. Then we assume that the statement is true for $F_{k-1}$ and $F_{k-2}$ and try to prove it for $F_k$.
Consider $F_{k-2}$:
If ${k-2}\equiv0\mod 3$, then both $k-1$ and $k$ are not divisible by $3$, so $F_{k-2}$ is even and $F_{k-1}$ is odd, so $F_k$ is odd.
If ${k-2}\equiv1\mod 3$, then $k-1\equiv2$ and $k\equiv0$, so $k-1$, $k-2$ are not divisible by $3$, hence $F_{k-1}$, $F_{k-2}$ must both be odd which makes $F_k$ even.
If ${k-2}\equiv2\mod 3$, then $k-1\equiv0$ and $k\equiv1$, so $F_{k-1}$ is even, $F_{k-2}$ is odd, which makes $F_k$ odd.
Thus, $F_k$ is even only when $k\equiv0 \mod3$
First of all, I'm not sure if this proof is valid, just because I think I might have done something wrong with the base cases or the inductive step. Please let me know if there is something wrong.
More importantly, however, when I looked at the hints for this problem, it said:
Try to prove that modulo $2$, $F_{3t} \equiv 0$, $F_{3t+1}\equiv 1$, and $F_{3t+2}\equiv 1$ for $t\geq0$.
Which is different from the strategy I used. Can someone show me how to prove using this method?