Sequence of distinct positive integers Given a sequence $\{a_n\}$ of distinct positive integers such that $\forall n\space a_n\geqslant 2\space$, prove that there exists a subsequence ${a_{i_k}}$ satisfying $a_{i_k}>i_k$ for all $k$.
 A: First, we notice that your question is equivalent to the following:
Equivalent Formulation: Infinitely often during the sequence $\{a_n\}$, we have $a_i > i$. If this warrants further explanation, please comment.
Now, by the well-ordering of the natural numbers, we know that $\{a_n\}$ can be ordered into another sequence, call it $\{b_n\}$. That is, for $i < j$, $b_i < b_j$ and the sets of terms in both sequences are the same. Now, it can be shown that for all $i$, $b_i > i$. This follows from the monotonicity of $\{b_n\}$ and the fact that $b_i \geq 2$ for all $i$.
Now, we notice that $a_i$ is a bijective function from the natural numbers to the terms of $\{b_n\}$. We use this fact, and others, in the following, to construct for any index $i$ a term $a_u$ of $\{a_n\}$ with $a_u > u > i$.
First consider the set $\{a_1, \dots, a_i\}$. It is finite and has a maximum element, call the maximum $a$. Now, eventually the sequence $\{a_n\}$ will surpass this maximum value, say at index $j$. At this point we will have that $a_j$ is the last element and the maximum of the prefix $\{a_1, \dots, a_j\}$.
Now, let's say that $a_j = b_m$ for some $m$. We know that $a_k < b_m$ for all $k < j$, by the maximality of $a_j$. Now consider the prefix of $\{b_n\}$ up to $m$, that is: $\{b_1, b_2, \dots, b_m\}$. There are exactly $m-j$ terms in this sequence that are not in $\{a_1, \dots, a_j\}$.
Now consider the set of terms $\{a_{j+1}, \dots, a_m\}$. There are two cases to consider:


*

*No $a$ in the set $\{a_{j+1}, \dots, a_m\}$ exceeds $b_m$. In this case, by bijectivity, $\{a_1, \dots, a_m\}$ = $\{b_1, \dots, b_m\}$ (set-wise, not ordered). But then $a_{m+1} \geq b_{m+1} > m + 1 > j > i$.

*Some $a$ in the set $\{a_{j+1}, \dots, a_m\}$ exceeds $b_m$. Call the index of this element $l$. Then $a_l > b_m > m \geq l > j > i$.


In either case, given some arbitrary index $i$, we have constructed a term $a_u > u > i$. Since the choice of $i$ is arbitrary, this must happen infinitely often. Q.E.D.
