Mock AIME II 2012 Problems/Problem 2
Problem
Let be a recursion defined such that
, and
where
, and
is an integer. If
for
being a positive integer greater than
and
being a positive integer greater than 2, find the smallest possible value of
.
Solution
The sequence goes as follows:
Note that this sequence repeats, because once we get to
, we subtract
from the number under the square root sign and take the square root of that, then when you take the difference of the squares of these two numbers, they have a difference of
, so you get back to
.
The first perfect square less than is
. Therefore
.
We present three ways to finding :
Way 1: Now notice that, for , we have
. Also, the terms under the radical counts down one for every
such that
. The number of
before a number
can be seen to be
. Therefore, we can see that
. Setting this equal to
, we see that
. We can see that both
and
satisfy this, however, since
, we disregard this, and we find that
, so
.
Way 2: Look at the sequence by grouping terms as follows:
. Note that the number of these groups of three that we have is equal to the number of terms in the sequence
. This has
terms in it. Before the last group, we have
terms, and
is therefore the
th term, and
.
Both ways lead to and
, so the answer is
.
To show that no smaller sums can be created, note that the next perfect square will be and will take more than
as the value of
, and hence all other perfect squares will take more than
, and we have
as our sum which is greater than
since
.
Way 3
We must ignore the cases where , as required by the problem statement. Write
for some integers
. We want to minimize
. Note if
is even (
is even) then
, and if
is odd (
is odd), then
. Rewrite
and note that
is at most
. In the case that
is odd, we have
. This is a quadratic in
and is strictly decreasing for
, so to minimize we should choose
, which gives
. Do the case for
even as well, you find that
is the lowest.