Difference between revisions of "2004 AIME II Problems/Problem 9"

(temporary saving)
(solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
Let <math>x = a_2</math>; then solving for the next several terms, we find that <math>a_3 = x^2,\ a_4 = x(2x-1),\ a_5 = (2x-1)^2,\ a_6 = (2x-1)(3x-2)</math>, and in general, <math>a_{2n} = [(n-1)x - (n-2)][nx - (n-1)],</math> <math> a_{2n+1} = [nx -(n-1)]^2</math>. This we can easily show by [[induction]]: since <math>a_{2n} = 2a_{2n-1} - a_{2n-2} = 2[(n-1)x-(n-2)]^2 - [(n-2)x-(n-3)][(n-1)x-(n-2)] = []</math>. The answer is <math>957 + 16</math>.
+
Let <math>x = a_2</math>; then solving for the next several terms, we find that <math>a_3 = x^2,\ a_4 = x(2x-1),\ a_5 = (2x-1)^2,\ a_6 = (2x-1)(3x-2)</math>, and in general, <math>a_{2n} = f(n-1)f(n)</math>, <math>a_{2n+1} = f(n)^2</math>, where <math>f(n) = nx - (n-1)</math>. This we can easily show by simultaneous [[induction]]: since  
 +
<center><math>\begin{align*}a_{2n} &= 2a_{2n-1} - a_{2n-2} = 2a_{2(n-1)+1} - a_{2(n-1)} \\
 +
&= 2f(n-1)^2 - f(n-2)f(n-1) \\
 +
&= f(n-1)[2f(n-1) - f(n-2)] \\
 +
&= f(n-1)[(2n-2-n+2)x-(2n-4-n+3)] \\
 +
&= f(n-1)f(n) \end{align*}</math></center>
 +
and
 +
<center><math>\begin{align*}a_{2n+1} &= \frac{a_{2n}^2}{a_{2n-1}} = \frac{f(n-1)^2f(n)^2}{f(n-1)^2} = f(n)^2 \\
 +
\end{align*}</math></center>
 +
From <cmath>a_9 + a_{10} = f(4)^2 + f(4)f(5) = (4x-3)(9x-7) = 646 = 2\cdot 17 \cdot 19</cmath>, we find that by either the [[quadratic formula]] or trial-and-error/modular arithmetic that <math>x=5</math>. Thus <math>f(n) = 4n+1</math>, and we need to find the largest <math>n</math> such that either <math>f(n)^2\, \mathrm{or}\, f(n)f(n-1) < 1000</math>. This happens with <math>f(7)f(8) = 29 \cdot 33 = 957</math>, and this is the <math>2(8) = 16</math>th term of the sequence.
 +
 
 +
The answer is <math>957 + 16 = \boxed{973}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 20:51, 8 June 2008

Problem

A sequence of positive integers with $a_1=1$ and $a_9+a_{10}=646$ is formed so that the first three terms are in geometric progression, the second, third, and fourth terms are in arithmetic progression, and, in general, for all $n\ge1,$ the terms $a_{2n-1}, a_{2n}, a_{2n+1}$ are in geometric progression, and the terms $a_{2n}, a_{2n+1},$ and $a_{2n+2}$ are in arithmetic progression. Let $a_n$ be the greatest term in this sequence that is less than $1000$. Find $n+a_n.$

Solution

Let $x = a_2$; then solving for the next several terms, we find that $a_3 = x^2,\ a_4 = x(2x-1),\ a_5 = (2x-1)^2,\ a_6 = (2x-1)(3x-2)$, and in general, $a_{2n} = f(n-1)f(n)$, $a_{2n+1} = f(n)^2$, where $f(n) = nx - (n-1)$. This we can easily show by simultaneous induction: since

$\begin{align*}a_{2n} &= 2a_{2n-1} - a_{2n-2} = 2a_{2(n-1)+1} - a_{2(n-1)} \\

&= 2f(n-1)^2 - f(n-2)f(n-1) \\ &= f(n-1)[2f(n-1) - f(n-2)] \\ &= f(n-1)[(2n-2-n+2)x-(2n-4-n+3)] \\

&= f(n-1)f(n) \end{align*}$ (Error compiling LaTeX. Unknown error_msg)

and

$\begin{align*}a_{2n+1} &= \frac{a_{2n}^2}{a_{2n-1}} = \frac{f(n-1)^2f(n)^2}{f(n-1)^2} = f(n)^2 \\ \end{align*}$ (Error compiling LaTeX. Unknown error_msg)

From \[a_9 + a_{10} = f(4)^2 + f(4)f(5) = (4x-3)(9x-7) = 646 = 2\cdot 17 \cdot 19\], we find that by either the quadratic formula or trial-and-error/modular arithmetic that $x=5$. Thus $f(n) = 4n+1$, and we need to find the largest $n$ such that either $f(n)^2\, \mathrm{or}\, f(n)f(n-1) < 1000$. This happens with $f(7)f(8) = 29 \cdot 33 = 957$, and this is the $2(8) = 16$th term of the sequence.

The answer is $957 + 16 = \boxed{973}$.

See also

2004 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 8
Followed by
Problem 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions