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.

$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.
