Fibonacci sequence divisible by 3?

Question

I have a recursion question for my combinatorial class. I'm looking at the Fibonacci sequence $f(n)=f(n-1)+f(n-2)$ for $n \geq 3$ with $f(1)=f(2)=1$.

I'm trying to prove that $f(n)$ is divisible by 3 if and only if $n$ is divisible by 4. I can see the idea by writing out terms of the sequence, but I'm not sure how to prove the pattern. Can anyone help me in the right direction?

Answer 1

Why don't you try with induction? From a quick look at the Fibonacci sequence, the period of the remainder after division by $3$ is $1,1,2,0,2,2,1,0$. I believe this is easy to prove using induction. But perhaps there is a nicer way, because the induction would be long and not very nice...

Answer 2

Just compute the Fibonacci sequence in $\mathbb{Z}_3$, which has only three numbers: $0, 1, 2$. If the result of an addition "overflows," just "wrap" it around, so that $2 + 2 = 1$.

$F_1 = 1$ and $F_2 = 1$ by definition. Then $F_3 = F_1 + F_2 = 1 + 1 = 2$. And $F_4 = F_2 + F_3 = 1 + 2 = 3$. But change it over to $F_4 = 0$.

Then $F_5 = F_3 + F_4 = 2 + 0 = 2$, $F_6 = F_4 + F_5 = 0 + 2 = 2$, and then $F_7 = F_5 + F_6 = 2 + 2 = 4$ which we wrap around to $= 1$. Which leads us to $F_8 = F_6 + F_7 = 2 + 1 = 3$ which wraps around to $= 0$.

Clearly the whole pattern is going to repeat, because $\mathbb{Z}_3$ will not unexpectedly sprout more numbers.

Answer 3

Hint: Prove by induction that $$f(n)-f(n-8)\text{ is divisible by }3.$$ For the inductive step use the fact that $$f(n)-f(n-8)=[f(n-1)+f(n-2)]-[f(n-9)+f(n-10)]$$$$=[f(n-1)-f(n-9)]+[f(n-2)-f(n-10)].$$

Answer 4

Binet's formula $$ F(n)=\frac{\varphi^n-\hat\varphi^n}{\sqrt{5}} $$ where $$ \varphi=\frac{1+\sqrt{5}}{2},\qquad\hat\varphi=\frac{1-\sqrt{5}}{2} $$ still holds “modulo $3$” provided we interpret it correctly. In the three element field $\mathbb{F}_3$, $2=5$ is not a square, but we can add a root $\alpha$ of the polynomial $x^2-2$ and consider the extension field $K=\mathbb{F}_3(\alpha)$.

The same proof of Binet's formula on the real numbers shows that the Fibonacci numbers modulo $3$ are of the form $$ F_3(n)=\frac{\varphi_3^n-\hat\varphi_3^n}{\alpha} $$ where $$ \varphi_3=\frac{1+\alpha}{2},\qquad\hat\varphi_3=\frac{1-\alpha}{2} $$ Let's compute when $\varphi_3^n-\hat\varphi_3^n=0$, that is, $$ \left(\frac{\varphi_3}{\hat\varphi_3}\right)^{\!n}=1 $$ Now $$ \frac{\varphi_3}{\hat\varphi_3}= \frac{1+\alpha}{1-\alpha}= \frac{1+2\alpha+\alpha^2}{1-\alpha^2}=-2\alpha=\alpha $$ because $\alpha^2=2$ and $K$ has characteristic $3$.

Thus $$ \left(\frac{\varphi_3}{\hat\varphi_3}\right)^{\!n} =\alpha^n $$ and this is $1$ exactly when $n$ is divisible by $4$, because $\alpha^2=2$ and $2^2=1$ (in $K$).