proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3

Question

I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers:

$$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv f_n \space mod \space 2$$

In other words, a Fibonacci number is even if and only if its index is divisible by 3. But I am having difficulty using induction to prove this. Proving the initial condition $n=0$ is easy:

$0\equiv 0\space mod \space 3 \iff 0 \equiv 0 \space mod \space 2$ is true.

But showing the $P(n)$ implies $P(n+1)$ is where I am having difficulty:

Assuming P(n) to be true, there is an integer p and q such that:

$$n = 3p \iff f_{n-1}+f_{n-2}=2q$$

But I'm not sure how to use this to demonstrate that $P(n+1)$ is true. What should I do to complete this proof?

Answer 1

Hint: Adapt your induction proof slightly as follows:

(1) Show that it holds for the first two cases.

(2) Show that $P(n)$ and $P(n+1)$ together imply $P(n+2)$.

Answer 2

As an earlier answer said, you have to show P for the first two cases. It's easier just to use strong induction. A few more hints:

Given P(0), ..., P(n)

"$n+1$ divisible by 3 $\implies f_{n+1} $ is even." should be easy to show if you think about the parity of $f_n$ and $f_{n-1}$.

For the other direction, it's easier to prove the contrapositive:

"$n+1$ not divisible by 3 $\implies f_{n+1}$ is odd." Think how many of $n$ and $n-1$ are divisible by 3.