2006 AIME II 第 11 题

Question

一个数列定义如下：

a_1 = a_2 = a_3 = 1

，且对所有正整数

n

，

a_{n+3} = a_{n+2} + a_{n+1} + a_n

。已知

a_{28} = 6090307

，

a_{29} = 11201821

，且

a_{30} = 20603361

，求

\sum_{k=1}^{28} a_k

除以

1000

的余数。

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.

答案

答案：834

知识点：递推求和数学归纳法

难度评级：2840

小提示：

计算前几个部分和，并将它们与数列本身比较，从中找出规律。

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

大提示：

用递推式归纳可得

2S_n = a_{n+2} + a_n

。

Induction using the recurrence shows

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

解答：

令

S_n = a_1 + \cdots + a_n

。我们断言

2S_n = a_{n+2} + a_n

，对

n = 1

成立，因为

2 = 1 + 1

。若它对

n

成立，则

\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}

这一步用到了递推式，归纳因而完成。

因此

S_{28} = \frac{a_{30} + a_{28}}{2}

= \frac{20603361 + 6090307}{2}

= 13346834

，除以

1000

的余数为

834

。

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 第 11 题

答案：834

难度评级：2840

小提示：

大提示：

解答：

其他年份的第 11 题