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

m
m (Solution: typo fixed.)
Line 43: Line 43:
  
  
Since <math>b_n</math> and <math>b_{n+1}</math> are integer, we can see <math>b_n is divisible by </math><math>b_{n+1}</math>
+
Since <math>b_n</math> and <math>b_{n+1}</math> are integer, we can see <math>b_n</math> is divisible by <math>b_{n+1}</math>
  
  

Revision as of 14:01, 18 March 2011

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

Solution 1

This question is guessable but let's prove our answer

\[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$ is divisible by $b_{n+1}$


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

Solution 2

If $a_{n} \ne \frac {2009}{a_{n+1}}$, then either \[a_{n} = \frac {a_{n}}{1} < \frac {a_{n} + 2009}{1 + a_{n+1}} < \frac {2009}{a_{n+1}}\]

or

\[\frac {2009}{a_{n+1}} < \frac {2009 + a_{n}}{a_{n+1} + 1} < \frac {a_{n}}{1} = a_{n}\]

All the integers between $a_{n}$ and $\frac {2009}{a_{n+1}}$ would be included in the sequence. However the sequence is infinite, so eventually there will be a non-integral term.

So $a_{n} = \frac {2009}{a_{n+1}}$, which $a_{n} \cdot a_{n+1} = 2009$. When $n = 1$, $a_{1} \cdot a_{2} = 2009$. The smallest sum of two factors which have a product of $2009$ is $41 + 49=\boxed {090}$

See also

2009 AIME I (ProblemsAnswer KeyResources)
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