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?
Best Answer
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.