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$?
Best Answer
$$f_{n+3}=f_{n+2}+f_{n+1}=f_{n+1}+f_n+f_{n+1}=2f_{n+1}+f_n$$
Since $2f_{n+1}$ is even, you get $f_{n+3}$ is even if and only if $f_n$ is even.
The statement follows now by induction : Check $P(1), P(2), P(3)$ and prove $P(n) \Rightarrow P(n+3)$.