APMO

First, let us assume that $r>2$, and take a positive integer $a\ge 1/(r-2)$. Then, if we let $a_n=a+\lfloor n/2\rfloor$ for $n=1,2,\dots$, the sequence $a_n$ satisfies the inequalities $$\sqrt{a_n^2+r{a}_{n+1}}\ge \sqrt{a_n^2+r{a}_n}\ge \sqrt{a_n^2+\left(2+\frac{1}{a}\right)a_n}\ge a_n+1=a_{n+2}$$ but since $a_{n+2}>a_n$ for any $n$, we see that $r$ does not satisfy the condition given in the problem.

Now we show that $r=2$ does satisfy the condition of the problem. Suppose $a_1,a_2,\dots$ is a sequence of positive integers satisfying the inequalities given in the problem, and there exists a positive integer $m$ for which $a_{m+2}>a_m$ is satisfied. By induction we prove the following assertion: (†) $a_{m+2k}\le a_{m+2k-1}=a_{m+1}$ holds for every positive integer $k$. The truth of $(†)$ for $k=1$ follows from the inequalities below $$2a_{m+2}-1=a_{m+2}^2-{\left(a_{m+2}-1\right)}^2\le a_m^2+2a_{m+1}-{\left(a_{m+2}-1\right)}^2\le 2a_{m+1}$$ Let us assume that $(†)$ holds for some positive integer $k$. From $$a_{m+1}^2\le a_{m+2k+1}^2\le a_{m+2k-1}^2+2a_{m+2k}\le a_{m+1}^2+2a_{m+1}<{\left(a_{m+1}+1\right)}^2$$ it follows that $a_{m+2k+1}=a_{m+1}$ must hold. Furthermore, since $a_{m+2k}\le a_{m+1}$, we have $$a_{m+2k+2}^2\le a_{m+2k}^2+2a_{m+2k+1}\le a_{m+1}^2+2a_{m+1}<{\left(a_{m+1}+1\right)}^2$$ from which it follows that $a_{m+2k+2}\le a_{m+1}$, which proves the assertion $(†)$.

We can conclude that for the value of $m$ with which we started our argument above, $a_{m+2k+1}=a_{m+1}$ holds for every positive integer $k$. Therefore, in order to finish the proof, it is enough to show that $a_{m+2k}$ becomes constant after some value of $k$. Since every $a_{m+2k}$ is a positive integer less than or equal to $a_{m+1}$, there exists $k=K$ for which $a_{m+2K}$ takes the maximum value. By the monotonicity of $a_{m+2k}$, it then follows that $a_{m+2k}=a_{m+2K}$ for all $k\ge K$.

---

Alternative solution.

We only give an alternative proof of the assertion $(†)$ in solution 1. Let $\{a_n\}$ be a sequence satisfying the inequalities given in the problem. We will use the following key observations:

a. If $a_{n+1}\le a_n$ for some $n\ge 1$, then $$a_n\le a_{n+2}\le \sqrt{a_n^2+2a_{n+1}}<\sqrt{a_n^2+2a_n+1}=a_n+1$$ hence $a_n=a_{n+2}$.

b. If $a_n\le a_{n+1}$ for some $n\ge 1$, then $$a_n\le a_{n+2}\le \sqrt{a_n^2+2a_{n+1}}<\sqrt{a_{n+1}^2+2a_{n+1}+1}=a_{n+1}+1$$ hence $a_n\le a_{n+2}\le a_{n+1}$.

Now let $m$ be a positive integer such that $a_{m+2}>a_m$. By the observations above, we must have $a_m<a_{m+2}\le a_{m+1}$. Thus the assertion $(†)$ is true for $k=1$. Assume that the assertion holds for some positive integer $k$. Using observation (a), we get $a_{m+2k+1}=a_{m+2k-1}=a_{m+1}$. Thus $a_{m+2k}\le a_{m+2k+1}$, and then using observation (b), we get $a_{m+2k+2}\le a_{m+2k+1}=a_{m+1}$, which proves the assertion $(†)$.