Proof by induction: $F_{3n-1}$ is even. Note: For this problem, I am using the definition of Fibonacci numbers such that $F_0 = 1, F_1 = 1, F_2 = 2$, and so on.
Here's my current work.
Proof.
The proof is by induction on n.
Basis step: For $n = 1, F_2 = 2$. $2|2$, so the statement is true for $n = 1$.
Induction hypothesis: Assume that the statement is true for some positive integer $k$. That is, $F_{3k-1}$ is even, in other words, $2|F_{3k-1}$.
Now I need to show that $2|F_{3k + 2}$. 
I know that $F_{3k + 2} = F_{3k + 1} + F_{3k}$, amongst other Fibonacci recurrences, but I'm not exactly sure how to get from $F_{3k-1}$ up to $F_{3k + 2}$ and prove it's even.
 A: $F_{3k}\equiv F_{3k+1} \pmod{2}$ by the induction hypothesis.
Then, $$F_{3k+2}\equiv F_{3k}+F_{3k+1}\equiv 2F_{3k}\equiv 0 \pmod2 $$
A: $$F_{3(m+1)-1}=F_{3m+1}+F_{3m}=(F_{3m}+F_{3m-1})+(F_{3m-1}+F_{3m-2})$$
$$=F_{3m-1}+F_{3m-2}+2F_{3m-1}+F_{3m-2}$$
$$\implies F_{3(m+1)-1}\equiv3  F_{3m-1}\pmod2$$
So, $2\mid F_{3(m+1)-1}\iff 2|F_{3m-1}$
A: In induction proofs, it is fairly often useful to strengthen the induction hypothesis. We will prove that for every positive integer $n$, $F_{3n-3}$ and $F_{3n-2}$ are odd, and $F_{3n-1}$ is even.
The result is true by inspection for $n=1$.
Now suppose that for a particular $k$ we have $F_{3k-3}$ and $F_{3k-2}$ odd  and $F_{3k-1}$ even. We will show that $F_{3k}$ and $F_{3k+1}$ are odd, and $F_{3k+2}$ is even. 
Since by the induction hypothesis $F_{3k-2}$ is odd, and $F_{3k-1}$ is even, it follows that $F_{3k}$ is odd.
Since $F_{3k-1}$ is even and $F_{3k}$ is odd, it follows that $F_{3k+1}$ is odd.
And finally because $F_{3k}$ and $F_{3k+1}$ is odd, $F_{3k+2}$ is even.
A: $F_{3k+2}=F_{3k+1}+F_{3k}$ and $F_{3k+1}=F_{3k}+F_{3k-1}$
So $F_{3k+2}=2F_{3k}+F_{3k-1}$
Since $F_{3k}$ is an integer, if $F_{3k-1}$ is even then $F_{3k+2}$ must be even.
