Question

Una sucesión se define como sigue: $a_1 = a_2 = a_3 = 1,$ y, para todo entero positivo $n,$ $a_{n+3} = a_{n+2} + a_{n+1} + a_n.$ Dado que $a_{28} = 6090307,$ $a_{29} = 11201821,$ y $a_{30} = 20603361,$ halla el residuo cuando $\sum_{k=1}^{28} a_k$ se divide entre $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.$

Respuesta

Respuesta: 834

Conceptos:recursión sumatoria inducción

Nivel de dificultad: 2840

Pista pequeña:

Calcula las primeras sumas parciales y compáralas con la propia sucesión para detectar un patrón.

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

Pista grande:

La inducción usando la recurrencia muestra $2S_n = a_{n+2} + a_n.$

Induction using the recurrence shows $2S_n = a_{n+2} + a_n.$

Solución:

Sea $S_n = a_1 + \cdots + a_n.$ Afirmamos que $2S_n = a_{n+2} + a_n,$ lo cual se cumple para $n = 1$ ya que $2 = 1 + 1.$ Si se cumple para $n,$ entonces $\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}$ por la recurrencia, lo que completa la inducción.

Por lo tanto $S_{28} = \frac{a_{30} + a_{28}}{2}$ $= \frac{20603361 + 6090307}{2}$ $= 13346834,$ cuyo residuo al dividir entre $1000$ es $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 Problema 11

Respuesta: 834

Nivel de dificultad: 2840

Pista pequeña:

Pista grande:

Solución:

El Problema 11 en otros años