Fibonacci sequence and the Principle of Mathematical Induction Consider the Fibonacci sequence, $F_n$. Prove that $2 ~\vert~ F_n$ if and only if $3 ~\vert~ n$, using the principle of mathematical induction. 
I know that I have to prove two implications here. Looking at the first implication (if $2 ~\vert~ F_n$, then $3 ~\vert~ n$) , I am a little confused as to how my base case would look: is it valid to say that $F_1=1$ is not divisible by $2$ and $n=1$ is not divisible by $3$ making the statement true for $n=1$?

Note: this statement is true when using the following convention that $F_1 = 1, F_2 = 1, F_{n+2} = F_{n+1}+F_n$  (instead of the other common convention where $F_0 = 1, F_1=1$)
In particular, this will require what is known as strong induction (keeping track of multiple entries at a time instead of only the previous one)
To prove the forward direction that if $2|F_n$ then $3|n$, it is equivalent to prove its contrapositive: if $3\nmid n$ then $2\nmid F_n$.
We may as well prove the other direction at the same time (since the proofs in this case in fact are identical).
Note that: $F_1 = 1$ and $F_2 = 1$ satisfies both conditions.
Assume for our induction hypothesis that $F_{k} \equiv \begin{cases} 1\mod 2 & \text{for}~3\nmid k\\ 0\mod 2 & \text{for}~3\mid k\end{cases}$ for all $k\leq n$
Then for $n+1$, you have three cases:  $\begin{cases} n+1\equiv 0\mod 3\\ n+1\equiv 1\mod 3\\ n+1\equiv 2\mod 3\end{cases}$


*

*First case: $n+1\equiv 0\mod 3$.  Then that implies that $n$ and $n-1$ are both not divisible by 3.  By induction hypothesis then, $F_n\equiv 1\mod 2$ and $F_{n-1}\equiv 1\mod 2$.  So, $F_{n+1} = F_n + F_{n-1} \equiv 1 + 1 \equiv 0\mod 2$ (thus proving the backwards direction).

*Second case: $n+1\equiv 1\mod 3$.  Then that implies that $n\equiv 0\mod 3$ and $n-1$ is not divisible by 3.  By induction hypothesis then, $F_n\equiv 0\mod 2$ and $F_{n-1}\equiv 1\mod 2$.  So, $F_{n+1}=F_n+F_{n-1}\equiv 0+ 1\equiv 1\mod 2$.

*Third case: $n+1\equiv 2\mod 3$.  Then that implies that $n-1\equiv 0\mod 3$ and $n$ is not divisible by 3.  By induction hypothesis then, $F_{n-1}\equiv 0\mod 2$ and $F_{n}\equiv 1\mod 2$.  So, $F_{n+1} = F_n + F_{n-1} \equiv 1+ 0\equiv 1\mod 2$.
As any integer that is not a multiple of 3 will fall into either the second or third cases above, the forward direction is also proven.
