ISL 2001 A5
by Wolstenholme, Aug 1, 2014, 9:18 PM
Find all positive integers 
such that
where
and 
for 
.
Solution:
First, I shall show by reverse induction that
for all nonnegative integers 
. For the base case, letting 
it suffices to show that 
which is trivial.
Now, assume that for some positive integer
we have that 
. I shall show that 
.
It clearly suffices to show that
, because adding this to 
then yields the desired result. But upon expansion this is equivalent to the following inequality: 
which we know to be true. Therefore the induction hypothesis holds.
Now, since $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} = \frac{a_i}{a_{i + 1}} + \frac{a_{i + 1}}{a_{i + 2}} + \dpts + \frac{a_{n - 1}}{a_n} \geq \frac{a_i}{a_{i + 1}} $ we have that
for all nonnegative integers .
This inequality clearly implies that all of the
are uniquely determined. Letting 
in 
we find that 
. Plugging in 
we find that 
. Continuing in this fashion we find that the only solution is given by 
.
I want to provide some motivation for this solution. The idea for finding comes from the greedy algorithm... by applying it to the problem we immediately get a solution, and then it is pretty likely that we want to show that this is the only solution. The greedy algorithm works by finding an that satisfies every time we plug in a new 
so it is natural to try to prove that must always hold, and then induction becomes apparent.
such that
where
and 
for 
.Solution:
First, I shall show by reverse induction that
for all nonnegative integers 
. For the base case, letting 
it suffices to show that 
which is trivial.Now, assume that for some positive integer
we have that 
. I shall show that 
.It clearly suffices to show that
, because adding this to 
then yields the desired result. But upon expansion this is equivalent to the following inequality: 
which we know to be true. Therefore the induction hypothesis holds.Now, since $ \frac{99}{100} - \frac{a_0}{a_1} - \frac{a_1}{a_2} - \dots - \frac{a_{i - 1}}{a_i} = \frac{a_i}{a_{i + 1}} + \frac{a_{i + 1}}{a_{i + 2}} + \dpts + \frac{a_{n - 1}}{a_n} \geq \frac{a_i}{a_{i + 1}} $ we have that
for all nonnegative integers .This inequality clearly implies that all of the
are uniquely determined. Letting 
in 
we find that 
. Plugging in 
we find that 
. Continuing in this fashion we find that the only solution is given by 
.I want to provide some motivation for this solution. The idea for finding
comes from the greedy algorithm... by applying it to the problem we immediately get a solution, and then it is pretty likely that we want to show that this is the only solution. The greedy algorithm works by finding an that satisfies every time we plug in a new 
so it is natural to try to prove that must always hold, and then induction becomes apparent.
August 2016
June 2016