2017 AMC 10A Problem 13

Problem 13 of 25IntermediateAlgebra Number Theory

Define a sequence recursively by

F_{0}=0,

~F_{1}=1,

and

F_{n}=

the remainder when

F_{n-1}+F_{n-2}

is divided by

3,

for all

n\geq 2.

Thus the sequence starts

0,

1,

1,

2,

0,

2,

\ldots.

What is

F_{2017}+F_{2018}+F_{2019}+F_{2020}+

F_{2021}+F_{2022}+F_{2023}+F_{2024}?

Show solution

Solution

Let us list out the first few values to see if we can find a pattern in this sequence.

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, \cdots

The pair

(F_8,F_9)=(0,1)=(F_0,F_1).

Because each later term is determined by the preceding two terms, the sequence therefore repeats every

8

terms. The desired answer is the sum of

8

consecutive numbers, which is fixed. This sum is

0 + 1 + 1 + 2 + 0 + 2

+ 2 + 1 = 9.

Thus, D is the correct answer.