Difference between revisions of "2007 AIME I Problems/Problem 14"
Mathgeek2006 (talk | contribs) (→Solution) |
Mathgeek2006 (talk | contribs) m |
||
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 1== | + | == Solution == |
+ | |||
+ | === Solution 1 === | ||
We are given that | We are given that | ||
Line 24: | Line 26: | ||
<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== | + | === 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> | 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 | 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 |
Revision as of 18:41, 25 January 2014
Problem
A sequence is defined over non-negative integral indexes in the following way: , .
Find the greatest integer that does not exceed
Solution
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.