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?
$\begingroup$
$\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 JeonSep 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$– Mark BennetSep 24, 2014 at 15:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
HINT : In mod $3$, $$\color{red}{1},1,2,0,2,2,1,0,\color{red}{1},1,2,0,\cdots$$
-
$\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