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 "2007 AIME I Problems/Problem 14"
(→‎Solution)
Line 4: Line 4:
 
Find the [[floor function|greatest integer]] that does not exceed <math>\frac{a_{2006}^{2}+a_{2007}^{2}}{a_{2006}a_{2007}}</math>
 
Find the [[floor function|greatest integer]] that does not exceed <math>\frac{a_{2006}^{2}+a_{2007}^{2}}{a_{2006}a_{2007}}</math>
  
−
== Solution ==
+
== Solution 1==
 
We are given that
 
We are given that
  
Line 23: Line 23:
  
 
<math>b_{2007}+\frac{1}{b_{2007}}< b_{2007}+\frac{1}{b_{2006}}= 225</math>. It is only a tiny bit less because all the <math>b_i</math> are greater than <math>1</math>, so we conclude that the floor of <math>\frac{a_{2007}^{2}+a_{2006}^{2}}{a_{2007}a_{2006}}= b_{2007}+\frac{1}{b_{2007}}</math> is <math>224</math>.
 
<math>b_{2007}+\frac{1}{b_{2007}}< b_{2007}+\frac{1}{b_{2006}}= 225</math>. It is only a tiny bit less because all the <math>b_i</math> are greater than <math>1</math>, so we conclude that the floor of <math>\frac{a_{2007}^{2}+a_{2006}^{2}}{a_{2007}a_{2006}}= b_{2007}+\frac{1}{b_{2007}}</math> is <math>224</math>.
 +
 +
== Solution 2==
 +
The equation <math>a_{n+1}a_{n-1}-a_n^2=2007</math> looks like the determinant <cmath>\left|\begin{array}{cc}a_{n+1}&a_n\\a_n&a_{n-1}\end{array}\right|=2007.</cmath>
 +
Therefore, the determinant of this matrix is invariant. Guessing that this sequence might be a linear recursion because of the matrix form given below, we define the sequence <math>b_n</math> defined by <math>b_1=b_2=3</math> and <math>b_{n+1}=\alpha b_n+\beta b_{n-1}</math> for <math>n\ge 2</math>. We wish to find <math>\alpha</math> and <math>\beta</math> such that <math>a_n=b_n</math> for all <math>n\ge 1</math>. To do this, we use the following matrix form of a linear recurrence relation
 +
 +
<cmath>\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).</cmath>
 +
 +
When we take determinants, this equation becomes
 +
 +
<cmath>\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\text{det}\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).</cmath>
 +
 +
We want <cmath>\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=2007</cmath> for all <math>n</math>. Therefore, we replace the two matrices by <math>2007</math> to find that
 +
 +
<cmath>2007=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\cdot 2007</cmath>
 +
<cmath>1=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)=-\beta.</cmath>
 +
Therefore, <math>\beta=-1</math>. Computing that <math>a_3=672</math>, and using the fact that <math>b_3=\alpha b_2-b_1</math>, we conclude that <math>\alpha=225</math>. Clearly, <math>a_1=b_1</math>, <math>a_2=b_2</math>, and <math>a_3=b_3</math>. We claim that <math>a_n=b_n</math> for all <math>n\ge 1</math>. We proceed by [[induction]]. If <math>a_k=b_k</math> for all <math>k\le n</math>, then clearly, <cmath>b_nb_{n-2}-b_{n-1}^2=a_na_{n-2}-a_{n-1}^2=2007.</cmath> We also know by the definition of <math>b_{n+1}</math> that
 +
 +
<cmath>\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\text{det}\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).</cmath>
 +
 +
We know that the RHS is <math>2007</math> by previous work. Therefore, <math>b_{n+1}b_{n-1}-b_n^2=2007</math>. After substuting in the values we know, this becomes <math>b_{n+1}a_{n-1}-a_n^2=2007</math>.  Thinking of this as a linear equation in the variable <math>b_{n+1}</math>, we already know that this has the solution <math>b_{n+1}=a_{n+1}</math>. Therefore, by induction, <math>a_n=b_n</math> for all <math>n\ge 1</math>. We conclude that <math>a_n</math> satisfies the linear recurrence <math>a_{n+1}=225a_n-a_{n-1}</math>.
 +
 +
It's easy to prove that <math>a_n</math> is a strictly increasing sequence of integers for <math>n\ge 3</math>. Now
 +
 +
<cmath>\frac{a_{2007}^2+a_{2006}^2}{a_{2007}a_{2006}}=\frac{a_{2007}}{a_{2006}}+\frac{a_{2006}}{a_{2007}}=\frac{225a_{2006}-a_{2005}}{a_{2006}}+\frac{a_{2006}}{a_{2007}}.</cmath>
 +
 +
<cmath>=225+\frac{a_{2006}}{a_{2007}}-\frac{a_{2005}}{a_{2006}}=225+\frac{a_{2006}^2-a_{2005}a_{2007}}{a_{2005}a_{2006}}.</cmath>
 +
 +
<cmath>=225-\frac{2007}{a_{2005}a_{2006}}.</cmath>
 +
 +
The sequence certainly grows fast enough such that <math>\frac{2007}{a_{2005}a_{2006}}<1</math>. Therefore, the largest integer less than or equal to this value is <math>224</math>.
  
 
== See also ==
 
== See also ==

Revision as of 18:40, 25 January 2014

Problem

A sequence is defined over non-negative integral indexes in the following way: $a_{0}=a_{1}=3$, $a_{n+1}a_{n-1}=a_{n}^{2}+2007$.

Find the greatest integer that does not exceed $\frac{a_{2006}^{2}+a_{2007}^{2}}{a_{2006}a_{2007}}$

Solution 1

We are given that

$a_{n+1}a_{n-1}= a_{n}^{2}+2007$, $a_{n-1}^{2}+2007 = a_{n}a_{n-2}$.

Add these two equations to get

$a_{n-1}(a_{n-1}+a_{n+1}) = a_{n}(a_{n}+a_{n-2})$
$\frac{a_{n+1}+a_{n-1}}{a_{n}}= \frac{a_{n}+a_{n-2}}{a_{n-1}}$.

This is an invariant. Defining $b_{i}= \frac{a_{i}}{a_{i-1}}$ for each $i \ge 2$, the above equation means

$b_{n+1}+\frac{1}{b_{n}}= b_{n}+\frac{1}{b_{n-1}}$.

We can thus calculate that $b_{2007}+\frac{1}{b_{2006}}= b_{3}+\frac{1}{b_{2}}= 225$. Now notice that $b_{2007}= \frac{a_{2007}}{a_{2006}}= \frac{a_{2006}^{2}+2007}{a_{2006}a_{2005}}> \frac{a_{2006}}{a_{2005}}= b_{2006}$. This means that

$b_{2007}+\frac{1}{b_{2007}}< b_{2007}+\frac{1}{b_{2006}}= 225$. It is only a tiny bit less because all the $b_i$ are greater than $1$, so we conclude that the floor of $\frac{a_{2007}^{2}+a_{2006}^{2}}{a_{2007}a_{2006}}= b_{2007}+\frac{1}{b_{2007}}$ is $224$.

Solution 2

The equation $a_{n+1}a_{n-1}-a_n^2=2007$ looks like the determinant \[\left|\begin{array}{cc}a_{n+1}&a_n\\a_n&a_{n-1}\end{array}\right|=2007.\] Therefore, the determinant of this matrix is invariant. Guessing that this sequence might be a linear recursion because of the matrix form given below, we define the sequence $b_n$ defined by $b_1=b_2=3$ and $b_{n+1}=\alpha b_n+\beta b_{n-1}$ for $n\ge 2$. We wish to find $\alpha$ and $\beta$ such that $a_n=b_n$ for all $n\ge 1$. To do this, we use the following matrix form of a linear recurrence relation

\[\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).\]

When we take determinants, this equation becomes

\[\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\text{det}\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).\]

We want \[\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=2007\] for all $n$. Therefore, we replace the two matrices by $2007$ to find that

\[2007=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\cdot 2007\] \[1=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)=-\beta.\] Therefore, $\beta=-1$. Computing that $a_3=672$, and using the fact that $b_3=\alpha b_2-b_1$, we conclude that $\alpha=225$. Clearly, $a_1=b_1$, $a_2=b_2$, and $a_3=b_3$. We claim that $a_n=b_n$ for all $n\ge 1$. We proceed by induction. If $a_k=b_k$ for all $k\le n$, then clearly, \[b_nb_{n-2}-b_{n-1}^2=a_na_{n-2}-a_{n-1}^2=2007.\] We also know by the definition of $b_{n+1}$ that

\[\text{det}\left(\begin{array}{cc}b_{n+1}&b_n\\b_n&b_{n-1}\end{array}\right)=\text{det}\left(\begin{array}{cc}\alpha&\beta\\1&0\end{array}\right)\text{det}\left(\begin{array}{cc}b_{n}&b_{n-1}\\b_{n-1}&b_{n-2}\end{array}\right).\]

We know that the RHS is $2007$ by previous work. Therefore, $b_{n+1}b_{n-1}-b_n^2=2007$. After substuting in the values we know, this becomes $b_{n+1}a_{n-1}-a_n^2=2007$. Thinking of this as a linear equation in the variable $b_{n+1}$, we already know that this has the solution $b_{n+1}=a_{n+1}$. Therefore, by induction, $a_n=b_n$ for all $n\ge 1$. We conclude that $a_n$ satisfies the linear recurrence $a_{n+1}=225a_n-a_{n-1}$.

It's easy to prove that $a_n$ is a strictly increasing sequence of integers for $n\ge 3$. Now

\[\frac{a_{2007}^2+a_{2006}^2}{a_{2007}a_{2006}}=\frac{a_{2007}}{a_{2006}}+\frac{a_{2006}}{a_{2007}}=\frac{225a_{2006}-a_{2005}}{a_{2006}}+\frac{a_{2006}}{a_{2007}}.\]

\[=225+\frac{a_{2006}}{a_{2007}}-\frac{a_{2005}}{a_{2006}}=225+\frac{a_{2006}^2-a_{2005}a_{2007}}{a_{2005}a_{2006}}.\]

\[=225-\frac{2007}{a_{2005}a_{2006}}.\]

The sequence certainly grows fast enough such that $\frac{2007}{a_{2005}a_{2006}}<1$. Therefore, the largest integer less than or equal to this value is $224$.

See also

2007 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_I_Problems/Problem_14&oldid=58884"