2006 AIME II Problems/Problem 11

Problem

A sequence is defined as follows and, for all positive integers Given that and find the remainder when is divided by 1000.

Solution

Define the sum as . Since , the sum will be:

$\begin{align*}s &= a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \\

&= a_{28} + \left(\sum^{30}_{k=4} a_{k} - \sum^{29}_{k=3} a_{k}\right) - \left(\sum^{28}_{k=2} a_{k}\right)\\ &= a_{28} + (a_{30} - a_{3}) - \left(\sum^{28}_{k=2} a_{k}\right) = a_{28} + a_{30} - a_{3} - (s - a_{1})\\ &= -s + a_{28} + a_{30}

\end{align*}$ (Error compiling LaTeX. Unknown error_msg)

Thus , and are both given; the last four digits of their sum is , and half of that is . Therefore, the answer is .

Solution 2

Brute Force. - not that difficult in this case because you only need to keep track of the last 3 digits.