2006 AIME II Problems/Problem 11

Revision as of 13:54, 25 November 2007 by Azjps (talk | contribs) (minor fixes)

Problem

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^{28}_{k=1} a_k$ is divided by 1000.

Solution

Define the sum as $s$. Since $a_n\ = a_{n + 3} - a_{n + 2} - a_{n + 1}$, the sum will be:

$s = (a_4 - a_3 - a_2) + (a_5 - a_4 - a_3) + \ldots (a_{30} - a_{29} - a_{28}) + a_{28}$
$s = (a_4+ a_5 \ldots a_{30}) - (a_3 + a_4 + \ldots a_{29}) - (a_2 + a_3 + \ldots a_{28}) + a_{28} + (a_1 - a_1)$

The first two groups telescope. The third resembles $s$.

$s\ = a_1 - a_3 + a_{28} + a_{30} - s$
$2s\ = a_{28} + a_{30}$
$s\ = \frac{a_{28} + a_{30}}{2}$

$a_{28}$ and $a_{30}$ are both given; the last four digits of their sum is $3668$, and half of that is $1834$. Therefore, the answer is $834$.

See also

2006 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 10
Followed by
Problem 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions