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?
Best Answer
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$).