2006 AMC 10B Problem 18
Let be a sequence for which , , and for each positive integer . What is ?
Show solution without answering
Key insight
Write out terms until 2 and 3 appear again. The sequence repeats every 6 terms, and 2006 leaves remainder 2, so use the second term.
Solution
1. The index is too big to reach step by step, so look for a repeating pattern. Each term is the one before it divided by the one before that.
2. Work out terms:
3. The pair has come back at . Each term depends only on the two before it, so from here the sequence repeats exactly. The pattern is terms long:
4. Divide: . After full rounds of , we are at position of the pattern.
5. So .
The answer is .
Why this works
When each term is built from the two before it, the sequence must repeat once two neighboring terms come back. A huge index like is a strong hint to look for that cycle. Find the length of the cycle, then use the remainder to find the position inside it.
Alternative approach
See why the cycle has length . Using the rule twice, . So each term is over the term three places back, and flipping twice gets back to the start: .
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Generate terms until a repeat appears:
Since and , and each term is determined by the two before it, the sequence repeats with period : for all .
Now , so .
The answer is .
Review in the AoPS books
- Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
- Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
- Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
- Intermediate Algebra, Chapter 17: More Sequences and Series (§17.1, §17.2)
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.