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 thought I had this question down, but while looking over my solution, I think I'm missing a step.

I want to show for $f_n$ the nth fibonacci number, that $f_n$ is divisible by $4$ if and only if $n$ is divisible by $6$.

I approach this with strong induction. I was able to prove the backward implication by assuming the result holds for all $f_k$ up to $n$, and rewriting $f_{n+1}=8f_{n-4}+5f_{n-5}$. Also, I was able to prove that $f_n$ is divisible by $2$, if and only if $n$ is divisible by $3$ by rewriting $f_{n+1}=2f_{n-1}+f_{n-2}$.

I guess it remains to show that $f_{n+1}$ divisible by $4$ implies that $n$ is even, and thus $n$ will be divisible by $6$, but I just can't figure out how to show this last part. I've messed with proofs by contradiction, the contrapositive, but have come up with nothing. How would one do that?

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

One way to look at it is to consider the sequence in $\mathbb{Z}/4\mathbb{Z}$. Same definition: $f_1=f_2=1$ and $f_{n+1}=f_{n}+f_{n-1}$. The sequence hence starts as follows: 1, 1, 2, 3, 1, 0, 1, 1, ... Clearly the sequence is periodic of period 6. You can probably find a way to write this hand-wavy argument more rigorously.

share|improve this answer
    
All I think you need to say is the sequence modulo 4 starts 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, that $f_{n+6} \equiv f_n \pmod{4}$ is the inductive hypothesis, and we know $f_{n-1}+f_{n-2} = f_{n}$ so $f_{n+6} = f_{n+5} + f_{n+4}$ –  Henry Mar 7 '11 at 0:15
add comment

Let's compute the Fibonacci sequence modulo $4$: $$0,1,1,2,3,1,0,1,\ldots$$ Here the sequence repeats, since $0,1$ is where we started. We get that $$F_n \equiv F_{n \mod{6}} \pmod{4},$$ since $F_n \mod{4}$ is cyclic, with cycle of size $6$. Examining the first $6$ remainders, we see that only $F_0 \equiv 0 \pmod{4}$, hence your question.

If you really wanted, you could rephrase this argument as complete induction.

It's easy to generalize this argument to other moduli - in general the sequence will be eventually periodic, perhaps with an initial prefix which is not repeated.

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.