Difference between revisions of "2007 AIME I Problems/Problem 14"
(→Solution 5 (using limits)) |
m (Fixed a minor error near the end - since the sequence is a0, a1, a2, ... , the third term would be a2, not a3.) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 3: | Line 3: | ||
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> | ||
+ | ==Solutions== | ||
=== Solution 1 === | === Solution 1 === | ||
+ | Define a function <math>f(n)</math> on the non-negative integers, as <cmath>f(n) = \frac{a_n^2 + a_{n+1}^2}{a_na_{n+1}} = \frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_{n}}</cmath> | ||
+ | We want <math>\left\lfloor f(2006) \right\rfloor</math>. | ||
+ | |||
+ | Consider the relation <math>a_{n+1}a_{n-1}=a_{n}^{2}+2007</math>. Dividing through by <math>a_{n}a_{n-1}</math>, we get | ||
+ | <cmath>.\phantom{------------} \frac{a_{n+1}}{a_{n}} = \frac{a_{n}}{a_{n-1}} + \frac{2007}{a_{n}a_{n-1}} \phantom{------------} (1)</cmath> | ||
+ | and dividing through by <math>a_{n}a_{n+1}</math>, we get | ||
+ | <cmath>.\phantom{------------} \frac{a_{n-1}}{a_{n}} = \frac{a_{n}}{a_{n+1}} + \frac{2007}{a_{n}a_{n+1}} \phantom{------------} (2)</cmath> | ||
+ | Adding LHS of <math>(1)</math> with RHS of <math>(2)</math> (and vice-versa), we get | ||
+ | <cmath>\frac{a_{n+1}}{a_{n}} + \frac{a_{n}}{a_{n+1}} + \frac{2007}{a_{n}a_{n+1}} = \frac{a_{n}}{a_{n-1}} + \frac{a_{n-1}}{a_{n}} + \frac{2007}{a_{n}a_{n-1}} </cmath> | ||
+ | i.e. | ||
+ | <cmath>f(n)+ \frac{2007}{a_{n}a_{n+1}} = f(n-1) + \frac{2007}{a_{n}a_{n-1}}</cmath> | ||
+ | Summing over <math>n=1</math> to <math>n=2006</math>, we notice that most of the terms on each side cancel against the corresponding term on the other side. We are left with | ||
+ | <cmath>f(2006) + \frac{2007}{a_{2006}a_{2007}} = f(0) + \frac{2007}{a_{1}a_{0}} </cmath> | ||
+ | We have <math>f(0) = 2</math>, and <math>2007/a_0a_1 = 2007/9 = 223</math>. So | ||
+ | <cmath>f(2006) = 2 + 223 - \frac{2007}{a_{2006}a_{2007}} = 224 + \left( 1 - \frac{2007}{a_{2006}a_{2007}}\right)</cmath> | ||
+ | Since all the <math>a_i</math> are positive, <math>(1)</math> tells us that the ratio <math>a_{n+1}/a_n</math> of successive terms is increasing. Since this ratio starts with <math>a_1/a_0 = 1</math>, this means that the sequence <math>(a_n)</math> is increasing. Since <math>a_2=672</math> already, we must have <math>a_{2006}a_{2007} > 672^2 > 2007</math>. It follows that <math>\left\lfloor f(2006) \right\rfloor = 224</math>. | ||
+ | |||
+ | === Solution 2 === | ||
We are given that | We are given that | ||
Line 24: | Line 43: | ||
<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 | + | === Solution 3 === |
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 | ||
Line 54: | Line 73: | ||
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>. | 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>. | ||
− | ===Solution | + | ===Solution 4 ( generalized )=== |
This is a more elementary and rigorous solution to a slightly generalized version. The defining recursive sequence is generalized to | This is a more elementary and rigorous solution to a slightly generalized version. The defining recursive sequence is generalized to | ||
Line 107: | Line 126: | ||
Using lemma 3, the largest integer less than or equal to this value would be <math>k + 1</math>. | Using lemma 3, the largest integer less than or equal to this value would be <math>k + 1</math>. | ||
− | === Solution | + | === Solution 5 (pure algebra)=== |
We will try to manipulate <math>\frac{a_0^2+a_1^2}{a_0a_1}</math> to get <math>\frac{a_1^2+a_2^2}{a_1a_2}</math>. | We will try to manipulate <math>\frac{a_0^2+a_1^2}{a_0a_1}</math> to get <math>\frac{a_1^2+a_2^2}{a_1a_2}</math>. | ||
Line 130: | Line 149: | ||
The greatest number that does not exceed this is <math>224</math> | The greatest number that does not exceed this is <math>224</math> | ||
− | === Solution | + | === Solution 6 (using limits) === |
Let's start by computing the first couple terms of the given sequence so we know what we're working with. It's given that <math>a_0 = a_1 = 0</math>, and solving for <math>a_2</math> and <math>a_3</math> using the given relation we get <math>a_2 = 672 = 3(224)</math> and <math>a_3 = 3(224^{2} + 223)</math>, respectively. It will be clear why I decided to factor these expressions as I did momentarily. | Let's start by computing the first couple terms of the given sequence so we know what we're working with. It's given that <math>a_0 = a_1 = 0</math>, and solving for <math>a_2</math> and <math>a_3</math> using the given relation we get <math>a_2 = 672 = 3(224)</math> and <math>a_3 = 3(224^{2} + 223)</math>, respectively. It will be clear why I decided to factor these expressions as I did momentarily. | ||
Line 138: | Line 157: | ||
Now we must consider whether this finding holds true for the rest of the sequence we're examining. First of all, notice that each time <math>n</math> increases by <math>1</math>, the degrees of both the numerator and denominator increase by <math>2</math>, because we are squaring the <math>n+1th</math> term in the numerator while the same term, appearing in the denominator, is being generated in part by squaring the term before it (seen in the relation <math>a_{n+1}^2 = (\frac{a_{n}^2 + 2007}{a_{n-1}})^2</math>). Thus, the degree of the numerator will always be one greater than the degree of the denominator; we have only to show that the other terms in the expression remain sufficiently small enough so as not to disturb the <math>\approx224:1</math> ratio between the two. | Now we must consider whether this finding holds true for the rest of the sequence we're examining. First of all, notice that each time <math>n</math> increases by <math>1</math>, the degrees of both the numerator and denominator increase by <math>2</math>, because we are squaring the <math>n+1th</math> term in the numerator while the same term, appearing in the denominator, is being generated in part by squaring the term before it (seen in the relation <math>a_{n+1}^2 = (\frac{a_{n}^2 + 2007}{a_{n-1}})^2</math>). Thus, the degree of the numerator will always be one greater than the degree of the denominator; we have only to show that the other terms in the expression remain sufficiently small enough so as not to disturb the <math>\approx224:1</math> ratio between the two. | ||
− | For the non-greatest terms in the expression to offset this ratio for values of <math>n</math> in the ballpark of <math>2006</math>, they would have to have massive coefficients, because or else they are dwarfed by the additional <math>224</math> attached to the leading term. Thankfully, this is not the case. Since we are simply squaring previous terms repeatedly to get new terms, we end up getting a sequence that is approximately equal to <math>\frac{224^k+224^{k-1}+224^{k-2} . . . }{224^{k-1}+224^{k-2} . . . }</math> for all <math>k\geq2</math>, | + | For the non-greatest terms in the expression to offset this ratio for values of <math>n</math> in the ballpark of <math>2006</math>, they would have to have massive coefficients, because or else they are dwarfed by the additional <math>224</math> attached to the leading term. Thankfully, this is not the case. Since we are simply squaring previous terms repeatedly to get new terms, we end up getting a sequence that is approximately equal to <math>\frac{224^k+224^{k-1}+224^{k-2} . . . }{224^{k-1}+224^{k-2} . . . }</math> for all <math>k\geq2</math>, whose <math>\lim_{k\to\infty}=</math> <math>\boxed{224}</math>. |
~anellipticcurveoverq | ~anellipticcurveoverq |
Latest revision as of 22:20, 29 June 2021
Contents
Problem
A sequence is defined over non-negative integral indexes in the following way: , .
Find the greatest integer that does not exceed
Solutions
Solution 1
Define a function on the non-negative integers, as We want .
Consider the relation . Dividing through by , we get and dividing through by , we get Adding LHS of with RHS of (and vice-versa), we get i.e. Summing over to , we notice that most of the terms on each side cancel against the corresponding term on the other side. We are left with We have , and . So Since all the are positive, tells us that the ratio of successive terms is increasing. Since this ratio starts with , this means that the sequence is increasing. Since already, we must have . It follows that .
Solution 2
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 . Using the equation and dividing both sides by , 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 3
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 .
Solution 4 ( generalized )
This is a more elementary and rigorous solution to a slightly generalized version. The defining recursive sequence is generalized to
where is a positive integer and
Lemma 1 : For , We shall prove by induction. From (1), . From the lemma, Base case proven. Assume that the lemma is true for some . Then, eliminating the using (1) and (2) gives
It follows from (2) that
where the last line followed from (1) for case .
Lemma 2 : For Base case is obvious. Assume that for some . Then it follows that
This completes the induction.
Lemma 3 : For
Using (1) and Lemma 2, for
Finally, using (3), for Using lemma 3, the largest integer less than or equal to this value would be .
Solution 5 (pure algebra)
We will try to manipulate to get .
Using the recurrence relation, Applying the relation to ,
We can keep on using this method to get that
This telescopes to
or
Finding the first few values, we notice that they increase rapidly, so . Calculating the other values, .
The greatest number that does not exceed this is
Solution 6 (using limits)
Let's start by computing the first couple terms of the given sequence so we know what we're working with. It's given that , and solving for and using the given relation we get and , respectively. It will be clear why I decided to factor these expressions as I did momentarily.
Next, let's see what the expression looks like for small values of . For , we get , the floor of which is clearly because the in the numerator is insignificant. Repeating the procedure for is somewhat messier, but we end up getting . It's not too hard to see that is much larger than the sum of the remaining terms in the numerator, and that is similarly a lot greater than the other term in the denominator. In fact, the second-largest term in the numerator is only barely larger than , while the second-largest term in the denominator is smaller than . Thus, the floor of this expression will come out to be as well.
Now we must consider whether this finding holds true for the rest of the sequence we're examining. First of all, notice that each time increases by , the degrees of both the numerator and denominator increase by , because we are squaring the term in the numerator while the same term, appearing in the denominator, is being generated in part by squaring the term before it (seen in the relation ). Thus, the degree of the numerator will always be one greater than the degree of the denominator; we have only to show that the other terms in the expression remain sufficiently small enough so as not to disturb the ratio between the two.
For the non-greatest terms in the expression to offset this ratio for values of in the ballpark of , they would have to have massive coefficients, because or else they are dwarfed by the additional attached to the leading term. Thankfully, this is not the case. Since we are simply squaring previous terms repeatedly to get new terms, we end up getting a sequence that is approximately equal to for all , whose .
~anellipticcurveoverq
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.