Is this solution wrong or correct ? First we have by an immediate induction that for all positive integers $n$, $n+1\leq a_{n+1}$. If for all positive integers, $ a_{n+1}=n+1$, then the problem is solved. Otherwise, let $n_0$ be the smallest positive integer such that $a_{n_{0}}\neq n_{0}$. Thus we have $a_{n_{0}}\geq n_{0}+1$ and again by an immediate induction, $a_{n}\geq n+1$ for all integers $n\geq n_{0}$. If for all $n\geq n_{0}$, $a_{n}=n+1$, then the problem is solved again. Otherwise, let $n_{1}$ be the smallest integer $\geq n_{0}$ such that $a_{n_{1}}\neq n_{1}+1$. Thus we have $a_{n_{1}}\geq n_{1}+2$ and by an immediate induction, for all integers $n\geq n_{1}$, $a_{n}\geq n+2$. If for all... We continue in this way until the sequence finally stabilizes. Note that this must always happen because we have $a_{n+1}\leq 2n$. I know there is an easier solution using the pigeonhole principle, but is what I wrote correct ? Thanks

NO. The minor mistake is in the indexing; when $a_{n+1} = n+1$ does not hold for all positive integers, there will exist a least $n_0$ such that $a_{n_0 + 1} \neq n_0+1$, thus $a_{n_0 + 1} \geq n_0+2$, etcetera. The major mistake is in the finish of the "proof". As you show there will exist $n_k$ such that $a_{n+1} \geq n + k + 2$ for all $n\geq n_k$, this will not eventually "stabilize", since $n$ is not fixed, and it also increases. For example, the sequence $a_n = 2n-2$ for $n\geq 2$ never "stabilizes", since $a_n - n = n-2$, thus is unbounded.

Credits to Valikk202 We know that $a_{k+1} \le 2k$ so $2k-1 \ge a_{k+1}-a_1 > a_{k+1}-a_2 > \ldots > a_{k+1}-a_{k} \ge 1$ If $a_{k+1}-a_j=k$, for some $j$, then the problem is solved. Otherwise by pigeonhole principle there will be a pair of indices $(i,j)$ such that $a_{k+1}-a_i \equiv a_{k+1}-a_j \pmod k$, so $a_j-a_i=k$.

exist $i$ and $j$ $a_1,a_2,...,a_{n+1}$ $a_i \equiv a_j$ mod$n$. $$a_i- a_j= n$$

It turns out that this problem can be generalized in some sense. For any increasing sequence that increases at most linearly, something like that (but slightly weaker) also holds. See here. I'm curious about the source of that problem.