Let be an integer. Find, with proof, all sequences of positive integers with the following
three properties:
(a). ; (b). for all ; (c). given any two indices and (not necessarily distinct)
for which , there is an index such
that .
Solution
The sequence is .
Proof 1
We will prove that any sequence , that satisfies
the given conditions, is an
arithmetic progression with as both the first term and the
increment. Once this is proved, condition (b) implies that . Therefore ,
and the sequence is just the even numbers from to . The
sequence of successive even numbers clearly satisfies all three conditions,
and we are done.
First a degenerate case.
If , there is only one element , and condition (b) gives or . Conditions (a) and (c) are vacuously
true.
Otherwise, for , we will prove by induction on that the
difference for all ,
which makes all the differences , i.e. the sequence is an arithmetic progression with as the first term and increment as promised.
So first the case. With , exists and is less
than by condition (a). Now since by condition (b) , we conclude that , and therefore
by condition (c) for some . Now, since , and can only be . So .
Now for the induction step on all values of .
Suppose we have shown that for all , . If we are done, otherwise , and by
condition (c) for some . This is
larger than , but smaller than by the inductive hypothesis. It then follows that , the only element of the sequence between and . This establishes the result for .
So, by induction for all ,
which completes the proof.
Proof 2
Let .
Notice that Then by condition (c), we must have . This implies that , or that . Then we have , and the rest is trivial.