Difference between revisions of "2007 AIME I Problems/Problem 14"
Mathgeek2006 (talk | contribs) (→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 19:40, 25 January 2014
Contents
Problem
A sequence is defined over non-negative integral indexes in the following way: ,
.
Find the greatest integer that does not exceed
Solution 1
We are given that
,
.
Add these two equations to get
.
This is an invariant. Defining for each
, the above equation means
.
We can thus calculate that . Now notice that
. This means that
. It is only a tiny bit less because all the
are greater than
, so we conclude that the floor of
is
.
Solution 2
The equation looks like the determinant
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
defined by
and
for
. We wish to find
and
such that
for all
. To do this, we use the following matrix form of a linear recurrence relation
When we take determinants, this equation becomes
We want for all
. Therefore, we replace the two matrices by
to find that
Therefore,
. Computing that
, and using the fact that
, we conclude that
. Clearly,
,
, and
. We claim that
for all
. We proceed by induction. If
for all
, then clearly,
We also know by the definition of
that
We know that the RHS is by previous work. Therefore,
. After substuting in the values we know, this becomes
. Thinking of this as a linear equation in the variable
, we already know that this has the solution
. Therefore, by induction,
for all
. We conclude that
satisfies the linear recurrence
.
It's easy to prove that is a strictly increasing sequence of integers for
. Now
The sequence certainly grows fast enough such that . Therefore, the largest integer less than or equal to this value is
.
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.