Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Related. – Cameron Buie Sep 9 '13 at 15:37
up vote 3 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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