3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$).

$\endgroup$
2
$\begingroup$

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)].$$

$\endgroup$
1
$\begingroup$

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...

$\endgroup$
1
  • $\begingroup$ I think this is quite good enough. Induction would be too much, in my opinion. $\endgroup$
    – John-Luke
    Oct 13 '15 at 21:46
1
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ "Mathematicians report new element of $\mathbb{Z}_3$!" $\endgroup$
    – Brian Tung
    Oct 13 '15 at 22:00

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.