Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 AIME I Problems/Problem 13"

(New page: == Problem == The terms of the sequence <math>(a_i)</math> defined by <math>a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}</math> for <math>n \ge 1</math> are positive integers. Find the m...)
 
(→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
 +
<math>a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}</math>
 +
 +
 +
<math>a_{n + 2}(1 + a_{n + 1})= a_n + 2009</math>
 +
 +
 +
<math>a_{n + 2}+a_{n + 2} a_{n + 1}-a_n= 2009</math>
 +
 +
 +
let put <math>n+1</math> into <math>n</math> now
 +
 +
 +
<math>a_{n + 3}+a_{n + 3} a_{n + 2}-a_{n+1}= 2009</math>
 +
 +
 +
and set them equal now
 +
 +
 +
<math>a_{n + 3}+a_{n + 3} a_{n + 2}-a_{n+1}= a_{n + 2}+a_{n + 2} a_{n + 1}-a_n</math>
 +
 +
 +
<math>a_{n + 3}-a_{n+1}+a_{n + 3} a_{n + 2}-a_{n + 2} a_{n + 1}= a_{n + 2}-a_n</math>
 +
 +
 +
let's rewrite it
 +
 +
 +
<math>(a_{n + 3}-a_{n+1})(a_{n + 2}+1)= a_{n + 2}-a_n</math>
 +
 +
 +
Let make it looks nice and let <math>b_n=a_{n + 2}-a_n</math>
 +
 +
 +
<math>(b_{n+1})(a_{n + 2}+1)= b_n</math>
 +
 +
 +
Since <math>b_n</math> and <math>b_{n+1}</math> are integer, we can see <math>b_{n+1}</math> is divisible by <math>b_n</math>
 +
 +
 +
But we can't have an infinite sequence of proper factors, unless <math>b_n=0</math>
 +
 +
 +
Thus, <math>a_{n + 2}-a_n=0</math>
 +
 +
 +
<math>a_{n + 2}=a_n</math>
 +
 +
 +
So now, we know <math>a_3=a_1</math>
 +
 +
 +
<math>a_{3} = \frac {a_1 + 2009} {1 + a_{2}}</math>
 +
 +
 +
<math>a_{1} = \frac {a_1 + 2009} {1 + a_{2}}</math>
 +
 +
 +
<math>a_{1}+a_{1}a_{2} = a_1 + 2009</math>
 +
 +
 +
<math>a_{1}a_{2} = 2009</math>
 +
 +
 +
To minimize <math>a_{1}+a_{2}</math>, we need <math>41 and 49</math>
 +
 +
 +
Thus, answer <math>= 41+49=\boxed {090}</math>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2009|n=I|num-b=12|num-a=14}}
 
{{AIME box|year=2009|n=I|num-b=12|num-a=14}}

Revision as of 23:11, 20 March 2009

Problem

The terms of the sequence $(a_i)$ defined by $a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}$ for $n \ge 1$ are positive integers. Find the minimum possible value of $a_1 + a_2$.

Solution

$a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}$


$a_{n + 2}(1 + a_{n + 1})= a_n + 2009$


$a_{n + 2}+a_{n + 2} a_{n + 1}-a_n= 2009$


let put $n+1$ into $n$ now


$a_{n + 3}+a_{n + 3} a_{n + 2}-a_{n+1}= 2009$


and set them equal now


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


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


let's rewrite it


$(a_{n + 3}-a_{n+1})(a_{n + 2}+1)= a_{n + 2}-a_n$


Let make it looks nice and let $b_n=a_{n + 2}-a_n$


$(b_{n+1})(a_{n + 2}+1)= b_n$


Since $b_n$ and $b_{n+1}$ are integer, we can see $b_{n+1}$ is divisible by $b_n$


But we can't have an infinite sequence of proper factors, unless $b_n=0$


Thus, $a_{n + 2}-a_n=0$


$a_{n + 2}=a_n$


So now, we know $a_3=a_1$


$a_{3} = \frac {a_1 + 2009} {1 + a_{2}}$


$a_{1} = \frac {a_1 + 2009} {1 + a_{2}}$


$a_{1}+a_{1}a_{2} = a_1 + 2009$


$a_{1}a_{2} = 2009$


To minimize $a_{1}+a_{2}$, we need $41 and 49$


Thus, answer $= 41+49=\boxed {090}$

See also

2009 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AIME_I_Problems/Problem_13&oldid=30885"