# Proof that every third Fibonacci number is even

Consider this list of Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811

Looking at this again to find the even numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811

This seems like a trivial proof by induction and case analysis. Basically, there are 3 cases:

• "Index" is divisible by 1: odd + odd
• "Index" is divisible by 2: odd + even
• "Index is divisible by 3: even + odd

I assume that I can use $f(4) = f(2) + f(3) = 1 + 1 = 2$, $f(5) = f(3) + f(4) = 1 + 2 = 3$, and $f(6) = f(4) + f(5) = 2 + 3 = 5$ as the base case. I'm struggling with how to formulate the inductive case at that point, though; can someone help me do that? (I'm trying to formalize what I said above).

• The Fibonacci numbers modulo 2 are $0, 1, 1, 0, 1, 1, 0, 1, 1, \dots$. Just prove that the pattern $0,1,1$ is periodic. – steven gregory Aug 8 '17 at 15:19
• More interestingly, if you number with $F_1=1, F_2=1, F_3=2 \dots$ it is possible to prove that $F_r$ is a factor of $F_{kr}$ - your example is $F_3=2$ – Mark Bennet Aug 8 '17 at 15:46
• $\forall m, n \in \mathbb{Z}_{> 2}: \gcd \left\{{F_m, F_n}\right\} = F_{\gcd \left\{{m, n}\right\}}$ this is more general. – adityaguharoy Aug 8 '17 at 16:44
• $F_{n}=F_{n-1}+F_{n-2}=(F_{n-2}+F_{n-3})+F_{n-2}=2 F_{n-2} + F_{n-3}\,$, so $F_n$ and $F_{n-3}$ have the same parity. – dxiv Aug 8 '17 at 20:29
• The proof of this fact is also addressed in math.stackexchange.com/questions/386988/… (with ordinary induction) and math.stackexchange.com/questions/488518/… (with strong induction). – David K Aug 8 '17 at 21:18

The Fibonacci numbers are $a_0=0$, $a_1=1$, $a_{n+2}=a_{n+1}+a_n$ for $n\ge0$. We have \begin{align}a_0 &= 0\quad\text{(even)} \\ a_1 &= 1\quad\text{(odd)} \\ a_2 &= a_1+a_0=1\quad\text{(odd)} \\ a_3 &= a_2+a_1=2\quad\text{(even)} \\ a_4 &= a_3+a_2=3\quad\text{(odd)} \\ a_5 &= a_4+a_3=5\quad\text{(odd)} \end{align} It is straightforward from here to prove by induction that $a_k$ is even and $a_{3k+1}$ and $a_{3k+2}$ are odd for all $k\ge0$.

Try formulating the induction step like this:

\begin{align}\Phi(n) = & \text{f(3n) is even {\bf and}}\\ & \text{f(3n + 1) is odd {\bf and}}\\ & \text{f(3n+2) is odd. } \end{align}

Then use induction to prove that $\Phi(n)$ is true for all $n$. The base case $\Phi(0)$ is as easy as usual; it's just $\text{“$0$is even and$1$is odd and$1$is odd”}$.

Formally, for $n\in \mathbb N\cup \{0\}$ let $P(n)$ be the statement $$\exists m_1,m_2,m_3\in \mathbb N\cup \{0\}\;(\;F(3n)=2m_1\land F(3n+1)=2m_2+1\land F(3n+2)=2m_3+1\;)$$ where $F(x)$ is the $x$-th Fibonacci number.

(i). Prove $P(0).$

(ii). Prove $$\forall n\in \mathbb N\cup \{0\}\;(P(n)\implies P(n+1)\;).$$ For example, for part of this, $F(3n+3)=F(3n+2)+F(3n+1)=(2m_3+1)+(2m_2+1)=2m'_1$ where $m'_1=m_3+m_2+1.$