2
$\begingroup$

Consider the Fibonacci sequence $1, 1, 2, 3, 5, 8, 13, 21, . . .$ where each term, after the first two, is the sum of the two previous terms. How many of the first $1000$ terms are divisible by 3?

$\endgroup$
2
  • 2
    $\begingroup$ The fact $(F_a,F_b)=F_{(a,b)}$ (so $F_a\mid F_b$ if $a\mid b$) might be helpful. $\endgroup$
    – Hanul Jeon
    Sep 24, 2014 at 15:16
  • $\begingroup$ Try dividing the first few by $3$ to see what happens. If you spot a pattern, then prove it persists. $\endgroup$ Sep 24, 2014 at 15:18

1 Answer 1

6
$\begingroup$

HINT : In mod $3$, $$\color{red}{1},1,2,0,2,2,1,0,\color{red}{1},1,2,0,\cdots$$

$\endgroup$
1
  • $\begingroup$ The first few are: 1 1 2 3-YES 5 8 13 21-YES 34 55 89 144-YES 233 377 610 987-YES 1597 2584 4181 6765-YES 10946 17711 28657 46368-YES 75025 121393 196418 317811-YES One out of four, but I don't know how to prove this. $\endgroup$ Sep 24, 2014 at 18:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .