Let $f(n)$ be the $n$th Fibonacci number.
Prove that $3\mid f(n) \iff 4\mid n$
I tried to use induction to prove it but I couldn't continue when I reached $n+1$ case.
Let $f(n)$ be the $n$th Fibonacci number.
Prove that $3\mid f(n) \iff 4\mid n$
I tried to use induction to prove it but I couldn't continue when I reached $n+1$ case.
Let $g(n)=f(n)\bmod 3$. Then $g(0)=0$, $g(1)=1$, and $g(n+1)=\big(g(n)+g(n-1)\big)\bmod 3$ for $n>0$. The next few values are $g(2)=1$, $g(3)=2$, $g(4)=(1+2)\bmod 3=0$, and $g(5)=2$. Continuing in that vein, we can compute the following values, where I’ve starred the rows in which $3\mid f(n)$:
$\begin{array}{c|c|cc} n&f(n)&g(n)&\\ \hline 0&0&0&*\\ 1&1&1\\ 2&1&1\\ 3&2&2\\ 4&3&0&*\\ 5&5&2\\ 6&8&2\\ 7&13&1\\ \hline 8&21&0&*\\ 9&34&1\\ \end{array}$
Can you see why I put a bar between $n=7$ and $n=8$? Remember, each value of $f$ or $g$ depends only on the immediately preceding two values. The induction with $g(n)$ is a little easier to see than the induction with $f(n)$.
Hint: use the recurrence three times to write $f_{n+1}=3f_{n-2}+2f_{n-3}$. Then use the induction hypothesis, and the fact that $3\mid 2a \Longleftrightarrow 3 \mid a$ for any integer $a$.
:)
HINT $\ $ Show $\rm\ f_{\:n} \equiv\: -f_{\:n-4}\pmod 3\:,\:$ which immediately yields the sought result.
The above congruence is a special case $\rm\:k = 4\:$ of a more general law: $\rm\:f_{\:n}\equiv f_{\:k-1}\ f_{\:n-k} \pmod{f_{\:k}}\:.\:$
This leads to a simple inductive proof that $\rm\:gcd(f_n,f_k) = f_{\:gcd(n,k)}\:,\ $ so $\rm\ f_{\:k}\ |\ f_{\:n}\ \iff\ k\ |\ n\:.\ $
Specializing $\rm\:k = 4\:$ yields $\rm\ 3\ |\ f_{\:n}\ \iff\ 4\ |\ n\:.$