Let be a sequence of positive real numbers, and be a positive integer, such that

Prove there exist positive integers and , such that


Proof:

So this took me quite a while to solve, so as I go through the proof I will include the motivation for each step.

The first thing to ask yourself is "how does grow"? What function seems to satisfy Well, clearly the answer is a function of the form for some constant This motivates the following lemma:

Lemma 1: Let such that for all Then for all

Proof: We proceed by strong induction. The base case when follows from the definition of Now for any we have for some positive integer that as desired.

Now, what are we looking for? Well, we want the sequence to follow a sort of pattern. Knowing its general asymptotics, we are motivated to do the following: let for all Note that by Lemma 1 this sequence consists only of nonnegative numbers.

If you've written out some sequences, it should be clear that our is exactly the that the problem asks to find. So wouldn't it be nice to rephrase what we want to prove in terms of the new sequence Well, after some searching, we find that in fact all we want to show is that for sufficiently large , we have that for all Let's write this as a lemma.

Lemma 2: To solve the problem, it suffices to show that for all sufficiently large we have

Proof: Note that which proves the lemma.

So, how can we show this? Well, we know that the sequence is bounded from below by so it would suffices to show that the sequence is weakly decreasing; namely, that for all Rephrasing this in terms of the original sequence of 's, we find that it suffices to show that but this follows immediately from the definition of the 's so we are done.