2007 AIME I Problems/Problem 14
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
.
Solution 3 ( 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
.
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.