Question

A sequence is defined as follows: $a_1 = a_2 = a_3 = 1,$ and, for all positive integers $n,$ $a_{n+3} = a_{n+2} + a_{n+1} + a_n.$ Given that $a_{28} = 6090307,$ $a_{29} = 11201821,$ and $a_{30} = 20603361,$ find the remainder when $\sum_{k=1}^{28} a_k$ is divided by $1000.$

Answer

Answer: 834

Concepts:recursion summation induction

Difficulty rating: 2840

Solution:

Let $S_n = a_1 + \cdots + a_n.$ We claim $2S_n = a_{n+2} + a_n,$ which holds for $n = 1$ since $2 = 1 + 1.$ If it holds for $n,$ then $\begin{aligned} 2S_{n+1} &= 2S_n + 2a_{n+1} \\ &= a_{n+2} + 2a_{n+1} + a_n \\ &= a_{n+3} + a_{n+1} \end{aligned}$ by the recurrence, completing the induction.

Therefore $S_{28} = \frac{a_{30} + a_{28}}{2}$ $= \frac{20603361 + 6090307}{2}$ $= 13346834,$ whose remainder upon division by $1000$ is $834.$

2006 AIME II Problem 11

Answer: 834

Difficulty rating: 2840

Solution:

Problem 11 in Other Years