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 题