# Strong Induction Proof: Fibonacci number even if and only if 3 divides index

The Fibonacci sequence is defined recursively by $F_1 = 1, F_2 = 1, \; \& \; F_n = F_{n−1} + F_{n−2} \; \text{ for } n ≥ 3.$ Prove that $2 \mid F_n \iff 3 \mid n.$

Proof by Strong Induction : $\bbox[5px,border:1px solid green]{\color{green}{n = 1 }}$ $2 \mid F_1$ is false. Also, $3 \mid 1$ is false.
The implication [False $\iff$ False] is vacuously true.

$\bbox[5px,border:1px solid green]{\color{green}{\text{Induction Hypothesis}}}$ Assume that $2 \mid F_i \iff 3 \mid n$ for every integer $i$ with $1 ≤ i ≤ k$.

$\bbox[5px,border:1px solid green]{\color{green}{k + 1 \text{th Case}}} \;$ To prove: $\quad 2 \mid F_{k + 1} \iff 3 \mid k + 1.$

$\bbox[5px,border:1px solid green]{\color{green}{n = k + 1 = 2}} \;$ $2 \mid F_2$ is false. Also, $3 \mid 2$ is false. So [False $\iff$ False] is vacuously true.

Hence assume that $k + 1 ≥ 3.$ We now consider three cases:

$\bbox[5px,border:1px solid green]{\color{green}{\text{Case 1: } k + 1 = 3q}}$ Thus $3 \require{cancel}\cancel{\mid} k$ and $3 \require{cancel}\cancel{\mid} (k − 1)$. By the ind hyp, $3 \require{cancel}\cancel{\mid} k \iff F_k$ odd & $3 \require{cancel}\cancel{\mid} (k − 1) \iff F_{k - 1}$ odd. Since $F_{k+1} = F_k + F_{k−1}$, thus $F_{k+1}$ = odd + odd = even.

$\bbox[5px,border:1px solid green]{\color{green}{\text{Case 2: } k + 1 = 3q + 1}}$ Thus $3 | k$ and $3 \require{cancel}\cancel{\mid} (k − 1).$ By the ind hyp, $3 | k \iff F_k$ even & $3 \require{cancel}\cancel{\mid} (k − 1) \iff F_{k - 1}$ odd. Thus $F_{k+1}$ odd.

$\bbox[5px,border:1px solid green]{\color{green}{{\text{Case 3: }} k + 1 = 3q + 2}}$ Thus $3 \require{cancel}\cancel{\mid} k$ and $3 | (k −1).$ By the ind hyp, $3 \require{cancel}\cancel{\mid} k \iff F_k$ odd and $3 \mid (k − 1) \iff F_{k - 1}$ even. Thus $F_{k+1}$ odd. $\blacksquare$

$\Large{1.}$ Does the proof clinch the $(\Leftarrow)$ of the $(k + 1)$th case?

$\Large{2.}$ Since the recursion contains $n, n - 1, n - 2$, thus the recursion "time lag" is $3$ here.
So shouldn't $3$ base cases be checked?

$\Large{3.}$ Further to #2, shouldn't "assume $k + 1 \geq \cancel{3} 4$" instead?

$\Large{4.}$ Shouldn't the $n = k + 1 = 2$ case precede the induction hypothesis?

I referenced 1. Source: Exercise 6.35, P152 of Mathematical Proofs, 2nd ed. by Chartrand et al

Supplement to peterwhy's Answer:

$\Large{1.1.}$ I wrongly believed that all 3 Cases proved the $\Leftarrow$. I now see that Case 1 is $\Leftarrow$ via a Direct Proof. Cases 2 and 3 are $\Rightarrow$ via a Proof by Contraposition. Nonetheless, how would one foreknow/prevision to start from $3 \mid n$ for both directions of the proof?

• – Cameron Buie Sep 9 '13 at 15:37
• @CameronBuie: Thanks. It's referenced as 1 in my OP. – Greek - Area 51 Proposal Sep 10 '13 at 0:29
• Can you prove that the remainders of the Fibonacci numbers forever repeat the period $0,1,1,0,1,1,0,1,1,0,1,1,\ldots$? Hint: Denote the remainder of $F_n$ by $R_n$, then (surprise!) $R_{n+2}\equiv R_{n+1}+R_n\pmod2$. And an induction with depth three shows that $R_{n+3}=R_n$ for all $n$. – Jyrki Lahtonen Sep 11 '13 at 9:07

Part 1 Case 1 proves $3\mid (k+1)\Rightarrow 2\mid F_{k+1}$, and Case 2 and 3 proves $3\cancel\mid (k+1)\Rightarrow 2\cancel\mid F_{k+1}$. The latter is actually proving the contra-positive of $2 \mid F_{k + 1} \Longrightarrow 3 \mid k + 1$ direction.

Part 2 You only need the statement to be true for $n=k$ and $n=k-1$ to prove the case of $n=k+1$, as seen in the 3 cases. Therefore, $n=1$ and $n=2$ cases are enough to prove $n=3$ case, and start the induction process.

Part 3 :)

Part 4 Probably a personal style? I agree having both $n=1$ and $n=2$ as base cases is more appealing to me.

• Thank you. I upvoted. Could you please respond to my supplement in my OP (For easier reading)? – Greek - Area 51 Proposal Sep 11 '13 at 7:44

Look at $F_n$ modulo $2$. You will find the pattern of congruences: $$1, 1, 0, 1, 1, 0, ...$$. This follows from the fact that $F_1 \equiv F_2 \equiv 1$ (mod $2$) and the recursive definition of the Fibonnaci numbers.

• My apologies, I just realized that your post was not about finding any proof but rather has specific questions about your own. Ill leave my post since I think the proof is good but let me know if it is off topic. – Patrick Sep 9 '13 at 15:49
• No worries. Thanks. – Greek - Area 51 Proposal Sep 10 '13 at 0:51

Since the period of $2$ in base $\phi^2$ is three places long = $0.10\phi\; 10\phi \dots$, and the fibonacci numbers represent the repunits of base $\phi^2$, then it follows that $2$ divides every third fibonacci number, in the same way that $37$ divides every third repunit in decimal (ie $111$, $111111$, $111111111$, etc).