2006 AIME II Problem 11

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

Compute the first several partial sums and compare them with the sequence itself to spot a pattern.

Induction using the recurrence shows

2S_n = a_{n+2} + a_n.

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.

Problem 11 in other years