2009 AIME II Problems/Problem 14
The sequence satisfies and for . Find the greatest integer less than or equal to .
The "obvious" substitution
An obvious way how to get the from under the square root is to use the substitution . Then the square root simplifies as follows: .
The new recurrence then becomes and .
We can now simply start to compute the values by hand:
We now discovered that . And as each is uniquely determined by , the sequence becomes periodic. In other words, we have , and .
Therefore the answer is
After we do the substitution, we can notice the fact that , which may suggest that the formula may have something to do with the unit circle. Also, the expression often appears in trigonometry, for example in the relationship between the sine and the cosine. Both observations suggest that the formula may have a neat geometric interpretation.
Consider the equation:
Note that for we have and . Now suppose that we have for some . Then our equation becomes:
Depending on the sign of , this is either the angle addition, or the angle subtraction formula for sine. In other words, if , then , otherwise .
We have . Therefore , , and so on. (Remember that is the constant defined as .)
This process stops at the first , where exceeds . Then we'll have and the sequence will start to oscillate.
Note that , and , hence is strictly between and . Then , and . Therefore surely .
Hence the process stops with , we then have . As in the previous solution, we conclude that , and that the answer is .
|2009 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|