2007 AIME I Problems/Problem 14
Find the greatest integer that does not exceed
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 .
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 .
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
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 .
|2007 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|