Proof that every third Fibonacci number is even

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

F(n)=F(n-1)+F(n-2)=F(n-2)+F(n-3)+F(n-2)=2f(n-2)+F(n-3).so now we can deduce that F(n-3) and F(n) have the same parity because 2F(n-2) is definitely even.