3
$\begingroup$

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?

2 Answers 2

6

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.

  • 0
    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}$2011-03-07
2

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.