2017 AMC 10A Problem 13

P11-15~3 minPrint

Modular Arithmetic Sequences & Series Compute small cases, spot the pattern, generalize

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 without answering

Key insight

The list repeats every 8 terms, so any 8 terms in a row make one full cycle, which adds up to 9.

Solution

Index $2017$ is far too big to reach by hand, so look for a repeating pattern.

Each new term is the sum of the two before it, then take the remainder after dividing by $3$ . Keep going from the start:

$n$	0	1	2	3	4	5	6	7	8	9
$F_n$	0	1	1	2	0	2	2	1	0	1

For example, $F_6 =$ remainder of $0 + 2 = 2$ , and $F_8 =$ remainder of $2 + 1 = 3$ , which is $0$ .
2. At $n = 8, 9$ the pair $0, 1$ appears again, exactly like $F_0, F_1$ . Each term depends only on the two before it, so from here the list repeats the same $8$ terms forever: $0, 1, 1, 2, 0, 2, 2, 1$ .
3. The question adds $8$ terms in a row ( $F_{2017}$ through $F_{2024}$ ). Any $8$ terms in a row cover each spot of the cycle exactly once, just starting at a different place. So their sum is the sum of one full cycle:
$0 + 1 + 1 + 2 + 0 + 2 + 2 + 1 = 9.$

The answer is $\boxed{\textbf{(D)}\ 9}$ .

Why this works

When each term is built from the two before it using remainders, there are only a few possible pairs, so the list must eventually repeat. Watch for the starting pair to come back; that gives the cycle length. A block of terms as long as the cycle always adds up to the same total, wherever it starts.

Alternative approach

If you want to check which terms these are: $2017 = 8 \times 252 + 1$ , so $F_{2017}$ matches $F_1 = 1$ . The eight terms are then $F_1$ through $F_8$ in the cycle: $1, 1, 2, 0, 2, 2, 1, 0$ , which add to $9$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Continue the sequence, reducing each sum mod $3$ :
$0,\ 1,\ 1,\ 2,\ 0,\ 2,\ 2,\ 1,\ 0,\ 1,\ 1,\ 2,\ \ldots$
After eight terms the pair $(0, 1)$ reappears at $F_8, F_9$ . Since each term depends only on the previous two, the sequence repeats from there with period $8$ .

The requested sum has exactly eight consecutive terms, so it covers one full period, in some rotation. Its value is the sum of one period:
$0 + 1 + 1 + 2 + 0 + 2 + 2 + 1 = 9.$

The answer is $\boxed{\textbf{(D)}\ 9}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
Introduction to Number Theory, Chapter 10: Units Digits