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
    $\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 '14 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$ – Mark Bennet Sep 24 '14 at 15:18
6
$\begingroup$

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

$\endgroup$
  • $\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$ – user3105485 Sep 24 '14 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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