some janky bounding stuff sketch: you can prove that eventually you get an $a_i$ s.t $a_i \leq a_{i+1}$. If equality holds we can verify that it'll forever be constant and we gud. anyways, in this situation, it's easy to prove that all $a_j$ for $j > i+1$ is bounded between $a_i$ and $a_{i+1}$. The sequence is nondecreasing, and hence it must be constant, alternates between $a_i$ and $a_{i+1}$, or eventually goes up somehow and when it reaches $a_{i+1}$ it is capped and becomes constant. counterexample for $r > 2$ is if we let $x > \tfrac{1}{r-2}$, the seq $x$, $x$, $x+1$, $x+1$ ... works

To show that $r>2$ does not work, just pick $a_n = \lfloor\tfrac n2\rfloor + C$ where $C>\tfrac{2020}{r-2}$ is large enough. The main point is to show that $r=2$ works. We give the following observations. Claim: There does not exist $n$ such that $a_n\leq a_{n+1}< a_{n+2}$. Proof: Assume not, then \begin{align*} &a_{n+1}+1\leq a_{n+2}\leq \sqrt{a_n^2+2a_{n+1}} \\ \implies &a_{n+1}^2+2a_{n+1}+1\leq a_n^2+2a_{n+1} \\ \implies &a_{n+1}^2+1\leq a_n^2 \end{align*}which contradicts $a_{n+1}\geq a_n$. $\blacksquare$ Claim: If $a_{n+1}\leq a_n$, then $a_n=a_{n+2}$. Proof: We have $a_{n+2}\leq\sqrt{a_n^2+2a_n} <a_n+1$ hence the claim. $\blacksquare$ Obviously the sequence cannot be strictly decreasing. Hence take $n$ such that $a_{n+1}\geq a_n$. Observe that $$ a_{n+1}\geq a_n \stackrel{\text{Claim 1.}}{\implies} a_{n+1}\geq a_{n+2} \stackrel{\text{Claim 2.}}{\implies} a_{n+1}=a_{n+3} $$The last two gives $a_{n+3}\geq a_{n+2}$. Thus by repeating this argument indefinitely, we get $a_{n+1}=a_{n+3}=a_{n+5}=\hdots=C$ $\max\{a_n,a_{n+2},a_{n+4},\hdots,\}\leq C$ Hence it suffices to show that the sequence $a_n,a_{n+2},\hdots$ eventually stabilizes. But this is obvious as it's non-decreasing (the problem said that) and bounded.

If $r > 2$, then let $r = 2 + \varepsilon$. Now we have Consider $M > \frac{1}{\varepsilon}$. Hence, take $a_n = a_{n + 1} = M$, we would have \[ a_n^2 + ra_{n + 1} \ge a_n^ 2+ 2a_n + 1 = (a_n + 1)^2 \]Therefore, \[ a_n \le a_{n + 2} \le \lfloor \sqrt{a_n^2 + ra_{n + 1}} \rfloor = a_n + 1 \]if $a_n = a_{n + 1} \ge M$. Therefore, taking the sequence $(a_1, a_2, a_3, \dots) = (M,M,M+1,M+1,M+2, \dots)$ contradicts the statement. Now, we'll show that $r = 2$ fullfill the requirements. Lemma 01. If $a_n \ge a_{n + 1}$, then $a_{n + 2} = a_n$. Proof. Notice that \[ a_n \le a_{n + 2} \le \sqrt{a_n^2 + 2a_{n + 1}} \le \sqrt{a_n^2 + 2a_n} < \sqrt{a_n^2 + 2a_n + 1} = a_n + 1 \]Since $a_{n + 2} \in \mathbb{Z}$, we then have $a_{n + 2} = a_n$. Lemma 02. We can't have $a_i < a_{i + 1} < a_{i + 2}$ for three consecutive indices. Proof. Suppose otherwise, that there exists such index. Then \[ a_{i + 2} \le \sqrt{a_i^2 + 2a_{i + 1}} < \sqrt{a_{i +1}^2 + 2a_{i + 1} } < \sqrt{a_{i + 1}^2 + 2a_{i + 1} + 1} = a_{i + 1} + 1 \]Hence, $a_{i + 2} \le a_{i + 1}$, contradicts the statement. Therefore, consider the first index when we have $a_k > a_{k + 1}$. This must exists due to Lemma 02. Then by Lemma 01, we have $a_{k + 2} = a_k$, which gives us $a_{k + 1} < a_{k + 2}$. By Lemma 02, we will have, $a_{k + 3} < a_{k + 2}$ again, and keep repeating the process. We will have that $a_{k} = a_{k + 2} = a_{k + 4} = \dots $. WLOG this constant appears on even index. Furthermore, notice that the odd index will have an increasing sequence, but bounded from above by Lemma 02, which means that odd index will eventually constant as well.

The answer is \(r=2\). \bigskip Proof of lower bound: Note the following: If \(a_n\le a_{n+1}\), then \(a_{n+2}\ge a_n\) and \[a_{n+2}\le\sqrt{a_n^2+2a_{n+1}}<\sqrt{a_{n+1}^2+2a_{n+1}+1}=a_{n+1}+1\]so \(a_{n+1}>a_{n+2}\). If \(a_n>a_{n+1}\), then \(a_{n+2}\ge a_n\) and \[a_{n+2}\le\sqrt{a_n^2+2a_{n+1}}<\sqrt{a_n^2+2a_n+1}=a_n+1,\]so \(a_n=a_{n+2}\). Hence we can select \(N\) such that \(a_N=a_{N+2}=a_{N+4}=\cdots\) and \(a_{N+1}\le a_{N+3}\le a_{N+5}\le\cdots\), which are bounded above by \(a_N\) and eventually constant. \bigskip Proof of upper bound: I claim taking \[a_n=\left\lceil\frac1{r-2}\right\rceil+\left\lfloor\frac n2\right\rfloor\]works. Indeed, for all \(K\ge\tfrac1{r-2}\), we have \begin{align*} \sqrt{K^2+rK}&\ge\sqrt{K^2+\left(2+\frac1K\right)K}=(K+1)^2,\\ \sqrt{(K-1)^2+rK}&\ge\sqrt{K^2-2K+1+\left(2+\frac1K\right)K}>K^2. \end{align*}Coupled with \(a_{n+2}=a_n+1\), the above two estimates prove the claim.

For proof for $r=2$, simply note that $max(a_i,a_{i+1})$ is non-increasing. Thus the sequence $a_n$ is bounded above. Thus $a_i \leq a_{i+2} \leq a_{i+4}....$ and this subsequence is also bounded above, thus $a_n=a_{n+2}$ for all sufficiently large $n$ (by taking cases on whether $i$ is even or odd). For $r>2$, taking $m,m,m+1,m+1,m+2,m+2,...$ where $m$ is a sufficiently large positive integer works for a counterexample.

First, notice from the problem condition that to force $a_{n+2} = a_n$, we must have that $$ra_{n+1} < 2a_n+1 \qquad (*)$$ Claim : The conditions do not hold for $r>2$. Proof: Take $a_1 = a_2 > \tfrac{1}{r-2}$. Now, for contradiction, assume that after some point, the sequence alternates between two values $a_{M+1} \ge a_M > \tfrac{1}{r-2}$. However, this implies that $$ra_{M+1} < 2a_M+1 \le 2a_{M+1}+1 \quad \Rightarrow \quad a_{M+1} \le \frac{1}{r-2}$$a contradiction. $\square$ Claim: For $r=2$ there exists some $M$ such that $a_{n+1} = a_n$ for every $ n \ge M$. Proof: We proceed by casework. Case 1 : $a_1 = a_2$. From $(*)$, we are done. Case 2 : $a_1 < a_2$. From $(*)$, while $a_{2k-1} < a_{2k}$, we have that $a_{2k} = a_2$ and $a_{2k-1} < a_{2k+1}$. We now show that at some point, $a_{2k-1} = a_{2k}$. Suppose not, that is, there is some "leap" where $a_{2k-1} < a_{2k} < a_{2k+1}$. However, from $(*)$, this implies that $$2a_{2k}+1 \ge (a_{2k}+1)^2 - (a_{2k}-1)^2 = 4a_{2k}$$which is impossible. Thus, we are done. Case 3: This proceeds similarly to case 2. From $(*)$, it is easily verified that if $a_{n+1} = a_n$ for all $n \ge M$, the problem condition is implied. $\square$ Remark: If you just write out a sequence of actual numbers and experiment with the problem conditions, you should intuitively find the answer. This problem follows very logically and does not require any exceptional mathematical creativity.

This is my first posting in aops . I am confused about my solution , pls anyone check my solution and help me to find my errors.

Attachments:
apmo 2.pdf (69kb)

A rough sketch. $r>2$ doesn't work by counterexample shown above. $r=2$ means that $a_i\leq max\{a_1,a_2\}$ (since $(x+1)^2=x^2+2x+1$). However it implies the problem since $a_{n+2}\ge a_n$.

dame dame

Solved with L567 - posting for storage. $\textbf{Claim:}$ $r=2$ satisfies the condition. $\textbf{Proof)}$ We get that $$\sqrt{a_n^2+2a_{n+1}} \geq a_{n+2} \geq a_n$$for all $n \in \mathbb{N}$. Notice that if $a_{n+1} \leq a_n$, then $a_{n+2} = a_n$. On the other hand if $a_{n+1} \geq a_n$, then $$(a_{n+1}+1)^2 > a_n^2+2a_{n+1} \geq a_{n+2}^2$$meaning therefore that $a_{n+1} +1 > a_{n+2}$ and consequently $a_{n+1} \geq a_{n+2}$. If $a_{n+1} \geq a_n$, then $a_{n+3} = a_{n+1} \geq a_{n+2}$ from which we get that $a_{n+2} \leq a_n$ and eventually $a_{n+2} = a_n$. $\square$ $\textbf{Claim:}$ $r > 2$ doesn't satisfy the condition. $\textbf{Proof)}$ Let $r = 2 + \epsilon$ for $\epsilon > 0$. Let $n \in \mathbb{N}$ such that $n > \frac{2}{\epsilon}$ and take $$a_i = n+\lfloor \frac{i-1}{2} \rfloor$$which clearly satisfies the inequality. $\blacksquare$

Suppose $r$ is greater than 2. Exist $a$ integer,such that $a \ge \frac{1}{r-2}$. Now let’s look at the following sequence $a_1=a,a_2=a,a_3=a+1,a_4=a+1,....$ Satisfies these conditions. Contradiction. Easy proof $r=2$.

Funny problem. We need to prove the following claims: Claim 1: $r=2$ works. Proof: Let $b_n=\max(a_n,a_{n+1})$ and $c_n= a_n+a_{n+1}$ then we have that: $$a_{n+2} \leq\sqrt{a_n^2+2a_{n+1}} \leq \sqrt{b_n^2+2b_{n}} \implies a_{n+2} \leq b_n$$But also we have $a_{n+1} \leq b_n$ then $b_{n+1}=\max(a_{n+1},a_{n+2}) \leq b_n$ so $\{b_n\}$ is bounded and this implies $\{c_n\}$ is bounded. But: $$ c_n=a_n+a_{n+1} \leq a_{n+1} + a_{n+2} =c_{n+1}$$So $\{c_n\}$ is non-decresing and bounded so is eventually constant this implies the claim. $\square$ Claim 2: If $r>2$ exists a sequence that satisfies the condition but it's not eventually periodic. Proof: Let $a_n = \lfloor\tfrac n2\rfloor + C$ then we have that $a_{n+2}=a_n +1$ and the sequence it's non-decresing so it's enough prove that: $$a_{n+2} \leq\sqrt{a_n^2+ra_{n+1}} \Longleftrightarrow (a_n+1)^2 \leq a_n^2 +ra_{n+1} \Longleftrightarrow 2a_n +1 \leq ra_{n+1} \Longleftarrow 2a_n +1 \leq ra_n \Longleftrightarrow \frac{1}{r-2} \leq a_n $$And that it's true if we take $C > \frac{1}{r-2} $. $\square$ This implies that the maximum $r$ that satisfies the problem is $2$. $\blacksquare$

First we show $r=2$ works. Observe that If $a_{n+1} \le a_n$, then $a_{n+2}=a_n$. This is because $a_n^2 \le a_{n+2}^2 < (a_n+1)^2$. Otherwise if $a_{n+1}>a_n$, then $a_n \le a_{n+2} \le a_{n+1}$. This is because $$a_n^2 \le a_{n+2}^2 \le a_n^2+2a_{n+1} \le a_{n+1}^2+1$$and the fact that $a_{n+2}^2 \le a_{n+1}^2+1$ implies we must have $a_{n+2} \le a_{n+1}$. It's not hard to see that the first sentences of each of the above bullet points are enough to imply the problem statement. To see that $r>2$ doesn't work, simply take the construction$$k,k,k+1,k+1,k+2,k+2,k+3,k+3, \dots$$for large enough $k$. It's not hard to see this works.

Suppose $r>2$. Then simply use $N, N, N+1, N+1, N+2, N+2, \ldots$ for some large enough $N$ -- in particular, if $r=2+\varepsilon$, then $N$ should be at least $1/\varepsilon$. This is motivated by using a simple greedy algorithm; take the largest value at each step, and an easy construction is to make chains of equality all of length 2, as used. This can be checked to work. We now show that $r=2$ works. We have $a_{n+2} \in \left[a_n, \sqrt{a_n^2+2a_{n+1}}\right]$ for all $n$. Lemma: If $a_{n+1}=a_n+1$ for any $n$, then we are done. Proof: Suppose for some $n$ that $a_{n+1}=a_n+1$. Then $a_{n+2} \in \left[a_n, \sqrt{a_n^2+2a_n+2} \right]$, so $a_{n+2} \in \{a_n, a_n+1\}$. If $a_{n+2}=a_n+1$: then the sequence is $\ldots, a_n, a_n+1, a_n+1$. So $a_{n+3} \in \left[a_n+1, \sqrt{(a_n+1)^2+2(a_n+1)} \right]$, which forces $a_{n+3}=a_n+1$. So if we ever have two adjacent terms equal, the sequence is constant thereafter, and we're done. If $a_{n+2}=a_n$: Then the sequence is $\ldots,a_n, a_n+1, a_n$. Then $a_{n+3} \in \left[a_n+1, \sqrt{(a_n+1)^2+2a_n} \right]$, which forces $a_{n+3}=a_n+1$ since $(a_n+2)^2 > (a_n+1)^2+2a_n$. So the sequence is $\ldots, a_n, a_n+1, a_n, a_n+1$, and will hence alternate between these two, and we're done. So we can now assume that $a_{n+1} \not = a_n+1$ for any $n$. $\blacksquare$ Claim 1: For any $n$, if $a_n \ge a_{n+1}$, then $a_{n+2}=a_n$. Proof: We have $a_n\le a_{n+2} \le \sqrt{a_n^2+2a_{n+1}} \le \sqrt{(a_n+1)^2-1}$, which forces $a_{n+2}=a_n$. $\blacksquare$ Claim 2: For any $n$, if $a_n < a_{n+1}$, then $a_{n+1} \ge a_{n+2}$. Proof: From $a_n<a_{n+1}$ we have $a_n\le a_{n+1}-1$, so $a_n^2 \le (a_{n+1}-1)^2$. So in fact $a_n^2 \le (a_{n+1}-1)^2-1$ since $a_{n+1}>a_n$ and we assumed $a_{n+1} \not=a_n+1$. Rearranging this gives $\sqrt{a_n^2+2a_{n+1}} \le a_{n+1}$. So $a_{n+2} \le \sqrt{a_n^2+2a_{n+1}}\le a_{n+1}$. $\blacksquare$ Now we finish by splitting into cases: Case 1: $a_1<a_2$. Then by Claim 2, $a_3\le a_2$, so by Claim 1, $a_2=a_4$. Now $a_3\le a_4$, so $a_5\le a_4$, so $a_6=a_4$. Similarly continuing, we get $a_2=a_4=a_6=a_8=\cdots$. Call this common value $A$. We have $A > a_1,a_3,a_5,\ldots$. Also, $a_{n+2} \ge a_n$ for all $n$, so $a_1 \le a_3 \le a_5\le \cdots$. So now $(a_1\le a_3 \le a_5\le \cdots)$ is a sequence of positive integers bounded above (by $A$), so it is eventually constant. Then the problem statement is true at this point onwards. Case 2: $a_1 > a_2$. Then $a_1=a_3$ by Claim 2, so $a_2 < a_3$. Now simply chop off $a_1$ and we are equivalent to Case 1, so we are done. Case 3: $a_1 = a_2$. Then the sequence is entirely constant using logic from the Lemma's proof.

$r=2$ case For some $n$ assume that $a_{n+2}=a_n+k$ where $k\geq 1$. Then, \[(a_n+k)^2\leq a_n^2 + 2a_{n+1}.\]Then, $a_{n+1} \geq k\cdot a_n + \frac12 k^2$. For all $k\geq 1$, this gives $a_{n+2}\leq a_{n+1}$. Thus, we also have $a_{n+3}=a_{n+1}$ by bounding. Then, note that all terms after this will be $\leq a_{n+1}$ Additionally, both sequences $a_{n+2\cdot x}$ and $a_{n+\text{odd}}$ have nondecreasing terms, so they must eventually be constant. Thus, this case is done. $\square$. $r>2$ case Note that $a_n = \frac{1}{r-2} + \lfloor \frac{n}{2}\rfloor$ works. Lower bound obviously works, and upper bound is fine because \[(a_n + 1)^2 \leq a_n^2 + (2+(r-2))a_n\].$\square$.

First, we prove that $r=2$ does indeed satisfy the conditions. We have \[a_n \le a_{n+2} \le \sqrt{a^2_n + 2a_{n+1}}.\]If at any point $a_{n+1}=a_n$ then $a_{n+2}\le \sqrt{a^2_n+2a_{n}}<a_n+1.$ Thus, $a_{n+2}=a_{n+1}$ leaving $a$ constant. Now, suppose for the sake of contradiction that $a$ is strictly increasing. Then, $a_n+2\le a_{n+2}\le \sqrt{a^2_n + 2a_{n+1}}$ which implies that $4a_n+4\le 2a_{n+1}$ so $2a_n+2\le a_{n+1}.$ Thus, $a_{n+2}\ge 4a_n+6\ge a_n+9$ Now, when we have $a_n+c\le a_{n+2}$ then $a_n^2+2a_nc+c^2\le a_n^2+2a_{n+1}$ so $a_{n+1}\ge a_nc+\frac{c^2}{2}\ge a_nc.$ Thus, $a_{n+2}\ge a_nc^2\le a_n+c^2-1.$ Hence, if \[a_n+c\le a_{n+2}\]then \[a_n+c^2-1\le a_{n+2}.\]Thus, $a_{n+2}$ is infinitely big, contradiction. $~$ Now, suppose $r>2.$ Picking $c$ that is large enough say $c>\frac{1}{r-2}$, then doing $a_1=c,a_2=c,a_3=c+1,a_4=c+1,a_5=c+2,\dots$ will work.

I haven't seen a solution identical to mine here, so probably this is wrong and I'm too tired to see why: for $r>2$ I took: $a_n=\frac12(n+1)$. $a_n \le a_{n+2}$ is clearly true, the other inequality reduces to $-1 \le \frac{n}{2}$. Now, the hard(er) part: if $r=2$. Sps that: $a_{2}\le a_{1}$. By a simple induction: $a_{2n} \le a_{2n-1}, a_{2n-1}=a_{1}$ for all positive integers $n$. But then $(a_{2n})_{n \ge 1}$ is bounded (by $0$ and $a_1$), it will eventually become constant and we're done. Now suppose: $a_{2} > a_{1}$, then by a similar induction: $a_2\ge a_{2n-1}, a_{2n}=a_2$ for all positive integers $n$, and we're also done in the same manner as in the first case.

For $r = 2$, notice that $max(a_n, a_{n+1})$ is constant, so we are done. For $r > 2$, simply consider $c, c, c+1, c+1, c+2, c+2, \ldots$. For this to work, simply we need $1 \leq (r-2)c$ for integer $c$. Since $r > 2$, this exists.

$r>2$ is trivial by constructions above. For $r=2$ we just show the sequence is bounded to finish. If $\text{max}\{a_1,a_2\}=A$ then we induct: if $a_n,a_{n+1}\le A$ we have \[a_{n+2}\le \left\lfloor \sqrt{a_n^2+2a_{n+1}}\right\rfloor\le \left\lfloor \sqrt{A^2+2A}\right\rfloor=A\]so we're done. $\blacksquare$