Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Related. –  Cameron Buie Sep 9 '13 at 15:37
    
@CameronBuie: Thanks. It's referenced as 1 in my OP. –  LePressentiment 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

3 Answers 3

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.

share|improve this answer
    
Thank you. I upvoted. Could you please respond to my supplement in my OP (For easier reading)? –  LePressentiment 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.

share|improve this answer
    
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. –  LePressentiment 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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.