Problem 5 · 2009 AMC 8
Easy
Algebra & Patterns
tribonaccirecurrence
A sequence of numbers starts with 1, 2, and 3. The fourth number of the sequence is the sum of the previous three numbers in the sequence: 1 + 2 + 3 = 6. In the same way, every number after the fourth is the sum of the previous three numbers. What is the eighth number in the sequence?
Show answer
Answer: D — 68.
Show hints
Hint 1 of 2
There's no clever shortcut to hunt for — the rule itself IS the tool. Each new term only needs the three just before it, so you can roll forward step by step.
Still stuck? Show hint 2 →
Hint 2 of 2
Keep a sliding window of the last three numbers; add them for the next term, then slide the window forward one.
Show solution
Approach: iterate the recurrence (sliding window of 3)
- Each term = sum of the previous three. Roll forward: 1, 2, 3, then 1+2+3 = 6, then 2+3+6 = 11, then 3+6+11 = 20, then 6+11+20 = 37, then 11+20+37 = 68.
- That 68 is the 8th term. Sanity check: terms should grow but not explode — each roughly doubles, and 37 → 68 fits, so we didn't skip or double-count a term.
- You'll meet this again: a rule like "each term = sum of the last few" is a recurrence (this one is the Tribonacci pattern, cousin of Fibonacci). For a small target index, just iterate — only reach for formulas when the index is huge.
Mark:
· log in to save