Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Try writing out the sequence mod 3. –  William D. Dec 7 '11 at 21:58
2  
If you know that $f$ commutes with $gcd$, then it's easy. See en.wikipedia.org/wiki/Fibonacci_number#Divisibility_properties. –  lhf Dec 7 '11 at 22:18
    
(continuing my comment) ... because $3=f(4)$. –  lhf Dec 7 '11 at 22:24
1  
Very related: math.stackexchange.com/questions/34788/… –  JavaMan Dec 7 '11 at 22:50
add comment

3 Answers

up vote 7 down vote accepted

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

share|improve this answer
1  
Very nice bringing out of the structure, in a concrete manner. –  André Nicolas Dec 8 '11 at 0:57
add comment

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

:)

share|improve this answer
add comment

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\:.$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.