Given a fibonacci sequence with $F(0)=7, F(1)=11, F(n)=F(n-1)+F(n-2)$. How to prove that $F(n)$ is divisible by $3$ if and only if $n-2$ is divisible by $4$.
The proof I can think of is to get the general term formula of $F$ then prove the divisibility. Does anyone have better methods?
On
$n=2$ it is true, you have to show the result for $n=4k+2$.
Let's do it recursively. Suppose that $g(n)=F(n)$ mod $3$ is $0$ mod $3$.
$g(n+1)=g(n-1)+g(n)=g(n-1)$, $g(n+2)=g(n+1)+g(n)=g(n-1)$, $g(n+3)=g(n+2)+g(n+1)=2g(n-1)$, $g(n+4)=g(n+3)+g(n+2)=3g(n-1)=0$.
If $n\neq 2$ mod 4. Show recursively that $g(n)\neq 0$ as above.
First prove $$F(n+4)\equiv -F(n)\mod 3.$$ This is indeed easy: \begin{align} F(n+4)&\equiv F(n+3)+F(n+2)=2F(n+2)+F(n+1)\\ &\equiv -F(n+2)+F(n+1)=-F(n+1)-F(n)+F(n+1)=-F(n) \end{align} Now consider the $4$ first values modulo $3$: $$F(0)\equiv 1,\quad F(1)\equiv-1, \quad F(2) \equiv 0,\quad F(3)\equiv-1.$$ Thus, for all $k\in\mathbf N$, F(2+4k)\equiv\pm F(2)=0$.
Remark: it is easy to check that $F(n)\bmod3$ is periodic and has period $8$. The period is: $$1,-1,0,-1,-1,1,0,1.$$