Induction – Proof by Induction for Even Fibonacci Numbers with 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)$.