2001 AIME II Problem 3

Question

The first four terms are

x_1 = 211,

x_2 = 375,

x_3 = 420,

and

x_4 = 523.

For

n \ge 5,

\begin{aligned} x_n &= x_{n-1} - x_{n-2} \\ &\quad {}+ x_{n-3} - x_{n-4}. \end{aligned}

Find the value of

x_{531} + x_{753} + x_{975}.

Answer

Substitute the recurrence for

x_{n-1}

into the formula for

x_n

to get

x_n = -x_{n-5}

The sequence repeats with period

10,

so reduce each subscript mod

10

and compute

x_5

from the given values

For

n \ge 6,

substitute the recurrence for

x_{n-1}:

\begin{aligned} x_n &= \\ &(x_{n-2} - x_{n-3} + x_{n-4} - x_{n-5}) \\ &\quad {}- x_{n-2} \\ &\quad {}+ x_{n-3} - x_{n-4} \\ &= -x_{n-5}. \end{aligned}

Hence

x_{n+10} = -x_{n+5} = x_n,

so the sequence has period

10.

Since

531,

753,

and

975

leave remainders

1,

3,

and

5

upon division by

10,

we get

x_{531} = x_1 = 211,

x_{753} = x_3 = 420,

and

x_{975} = x_5

= x_4 - x_3 + x_2 - x_1

= 523 - 420 + 375 - 211

= 267.

The sum is

211 + 420 + 267 = 898.

Problem 3 in other years