Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Related. –  Cameron Buie Sep 9 '13 at 15:37
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.