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?

$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – Henry Mar 7 '11 at 0:15
  • $\begingroup$ @Minh Can this fact be used to prove $p\rightarrow q$ and $q\rightarrow p$? $\endgroup$ – Hopmaths yesterday
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.