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?


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)$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.