Determining the even Fibonacci numbers.

Question

There is another question regarding this topic in MSE (here) but this question (in my point of view) isn't answered fully correct. I will explain why.

The problem in question is to determine which Fibonacci numbers are even. I was able to show, using mathematical induction, that $F_{3n}, n \in \mathbb N$ is always even (this is also done in the question linked). Altought, I believe this doesn't fully answer the problem $-$ in my thoughts, I should also show that every Fibonnaci number that doesn't assume the form $F_{3j}$, for some integer $j \in \mathbb N$ isn't even (is odd). But I am having some trouble trying to show this.

My further thoughts and concise problem. The only intuition I got to solve the problem was to notice the following: assume that we are dealing with a Fibonacci number $F_m$ such that $m$ isn't divisible by $3$. Then, we have two possible options: either $m = 3p + 1$ or $m = 3q + 2$, for some integers $p,q \in \mathbb N_0.$ Recall the task is to show that $F_m$ is odd.

Case 1. Let us show that every Fibonacci number of the form $F_{3p+1},$ where $p \in \mathbb N_0$, is odd (by mathematical induction). The base case is trivial: for $p=0,$ it yields $F_{3\times 0 + 1} = F_1 = 1$ which is odd (the same can be easily verified for $p=1$). Now, assume that $F_{3p+1}$ is odd, for some fixed integer $p \in \mathbb N_0.$ Then,

$$ F_{3(p+1)+1} = F_{3p+4} = F_{3p+3} + F_{3p+2} = F_{3(p+1)} + F_{3p+1} + F_{3p}$$ From here, it suffices to see that $F_{3(p+1)}$ and $F_{3p}$ are both even (we already showed this in the linked question) and that $F_{3p+1}$ is odd, by hypothesis. Since the sum of even and odd numbers is odd, it follows that $F_{3(p+1)+1}$ is odd, showing what we want.

Case 2. Analogue to case $1$.

Is this proof acceptable? And is my intuition right about the answer not being "fully correct" ?

Thanks for any help in advance.

Answer 1

Just show

$F_n$ is even iff $3\mid n$

by induction all at once. Admittedly, that involves cases again, but they simply consist of “odd+odd=even“, “odd+even=odd”, and “even+odd=odd”.

Answer 2

I think your proof works, although it would be instructive perhaps to see the $3p+2$ worked out.

In general though, as noted in a comment, we can show that for $n>3$, $F_n = F_{n-1}+F_{n-2}$ $= F_{n-2}+F_{n-3}+F_{n-2} $ $=2F_{n-2} + F_{n-3}$ showing $F_{n} -F_{n-3}$ is even and thus $F_{n}$ and $F_{n-3}$ have the same parity. Together with the base cases of $(F_1,F_2,F_3)=(1,1,2)$ this demonstrates that the pattern of odd, odd, even continues.

Looking at the Fibonacci sequence under various modular bases is a whole interesting topic, http://www.fq.math.ca/Scanned/1-2/vinson.pdf . The "rank of apparition" is the point in the sequence where the sequence reaches a multiple of a given modulus, so for$\bmod 2$ the rank of apparition is $3$.