Let us define \[ L = \max \left( |a_1|, \dots, |a_{4034}| \right). \] First, we show that odd $a_n$'s can't be too negative. The idea is that if $a_n$ is a large negative term, then it's the sum of two positive terms, say $a_i + a_j$ with $i \le j$. Then if $j>2017$ we take $a_{j-i}$ to get some even larger negative term. The hypothesis $n$ is odd ensures $i \ne j$. Claim: If $n$ is an odd positive integer, then $a_n \ge -L$. Proof. We proceed by induction with base cases $n = 1, 3, \dots, 4033$ being tautological. If $n \ge 4035$, by definition there exists an integer $k \le n/2$ such that \[ -a_n = a_k + a_{n-k}. \]Since $n-k \ge n/2 > 2017$, we have \[ -a_{n-k} = \max_{i+j=n-k} (a_i+a_j) \ge a_k + a_{n-2k}. \]Consequently, $a_n = -(a_k + a_{n-k}) \ge a_{n-2k} \ge -L$, as $n-2k$ is an odd integer. $\blacksquare$ Once we have this we are home free. Claim: We have $a_n \le 2L$ for every positive integer $n$. Proof. Assume $n \ge 2018$ or there is nothing to prove. If $n$ is even, then $-a_n = \max_{i+j=n}(a_i + a_j) \ge a_1 + a_{n-1} \ge -2L$. Similarly if $n$ is odd, then $-a_n = \max_{i+j=n}(a_i + a_j) \ge a_2 + a_{n-2} \ge -2L$. $\blacksquare$ Claim: For any positive integer $n$, we have $a_n \ge -4L$. Proof. Assume $n \ge 2018$ or there is nothing to prove. Then $-a_n = \max_{i+j=n}(a_i+a_j) \le 2L+2L = 4L$, so $a_n \ge -4L$. $\blacksquare$ These three claims imply the result. Remark: It is conjectured that the sequence is periodic when the initial terms are integers, however I am not aware of any proof.

First assume that the sequence $(a_n)$ is bounded above by some real $M$. Then for any $n > 2017$ we have $$a_n = -\max_{i + j = n}(a_i + a_j) \geq -2M$$ Which implies that $(a_i)$ is also bounded below, and is therefore bounded. Henceforth assume that $(a_n)$ is not bounded above. Let $m = \min_{1 \leq i \leq 2017} a_i$ and choose an index $N$ such that $-2a_N < m$, $a_N > a_k$ for $k < N$, and $a_N$ is positive. This index must exist because the sequence is not bounded above. We will now show that $a_n \leq a_N$ for all $n$, contradicting that the sequence is not bounded above. We will prove by induction on $n$ that $-2a_N \leq a_n \leq a_N$ for all $n$. The base cases are all integers less than or equal to $N$, which we now prove. The fact that $a_n \leq a_N$ is true for the base cases by our choice of $a_N$. We now establish that $a_n \geq -2a_N$. For $1 \leq n \leq 2017$ this holds by our choice of $n$, while for $2017 < n < N$ we have $$a_n = -\max_{i + j = n}(a_i + a_j) > -2a_N$$ Because $a_i, a_j$ are both less than $a_N$. This establishes our base cases. Now assume the result is true for all $n \in \{1, 2, \dots, k\}$. By definition $$a_{k + 1} = -\max_{i + j = k + 1}(a_i + a_j)$$ By the inductive hypothesis we have $a_i + a_j \leq 2a_N$ and thus $a_{k + 1} \geq -2a_N$. For the other inequality, notice that $$-\max_{i + j = k + 1}(a_i + a_j) \leq -(a_N + a_{k + 1 - N}) \leq a_N$$ Because $a_{k + 1 - N} \geq -2a_N$. This establishes the inductive hypothesis and the desired contradiction.

Here is my really funny solution. I was surprised that no one at MOP came up with this when it was given on a test. For each $n>2017$, some $k<n$ has $a_k+a_{n-k}+a_n=0$, and for all $k<n$ we have $a_k+a_{n-k}+a_n \le 0$. Now, I claim the consecutive differences $|a_{n+1}-a_n|$ is bounded. Given $n \ge 2017$ with $a_n+a_k+a_{n-k}=0$, note that $a_{n+1}+a_k+a_{n-k+1} \le 0$ so that $(a_{n+1}-a_n)+(a_{n-k+1}-a_{n-k}) \le 0$ so that $a_{n+1}-a_n \le a_{n-k}-a_{n-k+1}$. Now say we are given $j$ with $a_{n+1}+a_j+a_{n+1-j}=0$, and assume without loss of generality that $j>10$ (else interchange $j, n+1-j$). Then $a_n+a_{j-1}+a_{n+1-j} \le 0$, so we have that $a_{n+1}-a_n+a_j-a_{j-1} \ge 0$, and so $a_{n+1}-a_n \ge a_{j-1}-a_j$. In any case, if up to say $r=9000$ the differences $a_{r+1}-a_r$ are bounded above and below by $C, -C$ respectively the two inequalities $a_{n+1}-a_n \le a_{n-k}-a_{n-k+1}$ and $a_{n+1}-a_n \ge a_{j-1}-a_j$ show that $a_{n+1}-a_n$ also satisfies these bounds. Thus consecutive differences of the sequence are bounded by some positive constant $C$. Since, $2a_n-C+a_1 \le a_1+a_n+a_{n+1} \le 0$ it follows that the sequence is eventually bounded above, and thus for some $a_n \le K$ always. But then for all large $n$, $a_n \ge -2K$ and so the sequene is also bounded below. We are done.

The following generalized version is proved in the SL book: Quote: A sequence of real numbers $a_1,a_2,\ldots$ satisfies the relation $$a_n=-\max_{i_1+i_2+...+i_k=n}(a_{i_1}+a_{i_2}+...+a_{i_k})\qquad\text{for all}\quad n>2017.$$Then, this sequence is bounded.

We start by defining sequences $b_{2018}, b_{2019}, \ldots $ and $c_{2018}, c_{2019}, \ldots $ that satisfies $$ b_n= \max(a_1, a_2, \ldots , a_n) $$$$ c_n= -\min(a_1, a_2, \ldots , a_n) $$for every integer $n\geq 2018$. Note that those sequences are non-decreasing. We will prove the following lemma. Lemma 1: $b_n\geq 0$ and $c_n\geq 0$ for every integer $n\geq 2018$. Proof. Since $a_{2018}=-\max_{i+j=2018}(a_i+a_j)$, the numbers $a_1, a_2, \ldots, a_{2018}$ cannot be all positive or all negative. Hence, there are at least one non-negative and one non-positive real number among them, yielding $b_{2018}\geq 0$ and $c_{2018}\geq 0$. But the sequences ${b_n}$ and ${c_n}$ are non-decreasing, so we are done. Lemma 2: If $c_k>2b_k$ for some integer $k\geq 2018$, then $c_{k+1}=c_k$. Proof. Notice that $$-a_{k+1}=\max_{i+j=k+1}(a_i+a_j)\leq 2b_k<c_k$$ However, we can check that $c_{k+1}=\max(c_k, -a_{k+1})$, so we are done. Lemma 3: If $c_k\leq 2b_k$ for some integer $k\geq 2018$, then $b_n=b_k$ and $c_n\leq 2b_k$ for every integer $n\geq k$. Proof. We only need to prove that $b_{k+1}=b_k$ and $c_{k+1}\leq 2b_k$ because after that, by induction, lemma 3 would be proved. Let $u\leq k$ be a positive integer such that $a_u=b_k$. Then, we have $$-a_{k+1}=\max_{i+j=k+1}(a_i+a_j)\geq a_u+a_{k+1-u}\geq b_k-c_k\geq -b_k$$ so $a_{k+1}\leq b_k$ and thus $b_{k+1}=b_k$. Meanwhile, $-a_{k+1}=-\max_{i+j=k+1}(a_i+a_j)\geq 2b_k$ so $c_{k+1}=\max(c_k, -a_{k+1})\leq 2b_k$. We are done. Now, if $c_n>2b_n$ for every $n\geq 2018$, then by lemma 2 we have $c_n=c_{2018}$ and thus $b_n<\frac{c_{2018}}{2}$ for every $n\geq 2018$. This means that $\frac{c_{2018}}{2}>a_n\geq -c_{2018}$ for every $n\in \mathbb{N}$. Otherwise, if $c_k\leq 2b_k$ for some $k\geq 2018$, by lemma 3 we would have $b_k=b_n\geq a_n\geq -c_n\geq -2b_k$ if $n\geq k$ and $b_k\geq a_n\geq -c_k\geq -2b_k$ if $n<k$. Either way, the sequence ${a_n}$ is bounded.

Denote $Y = 2017$ (it's arbitrary). The sequence relation can be rewritten as the pair $$\begin{aligned} \forall i, j &\colon i+j>Y \implies a_i+a_j+a_{i+j} \le 0; \quad &(1) \\ \forall n>Y \, \exists i, j &\colon (i+j=n) \land (a_i+a_j+a_n=0).\quad&(2) \end{aligned}$$First, we show that $(a_n)$ is bounded above. Assume the opposite. Let $$L=\max_{n \le Y} \left(\max \left(a_n, -\frac {a_n} 2\right)\right). \quad(3)$$Let $m$ be the minimum index such that $a_m>L$ and let $k>0$ be the minimum number such that $$a_{m+k}>a_m>L. \quad(4)$$$(3)$ and $(4)$ imply $m+k>Y$. $(1)$ shows that $a_m+a_{m+k} \le -a_k$, from $(4)$ it follows that $L<-\tfrac {a_k} 2$. $(3)$ shows that $k>Y$ and we can apply $(2)$: $\exists i, j \colon (i+j=k) \land (a_i+a_j+a_k=0)$. So $2a_m\!< a_m+a_{m+k} \le -a_k=a_i+a_j$. WLOG, $a_i \le a_j$. Then $a_m<a_j$ and the definition of $k$ shows that $j \ge m+k$ (note that $j<m$ is impossible as this would contradict the definition of $m$). But $j<i+j=k<m+k$, a contradiction. Now, as $(a_n)$ is bounded above, $\forall n \colon a_n \le U$, it is easy to prove that it is bounded below. Just apply $(2)$ to any $n>Y$: $a_n=-a_i-a_j \ge -2U$. $\blacksquare$ ThE-dArK-lOrD wrote: The following generalized version is proved in the SL book: That's very intriguing! I guess somewhere there is a book in which all problems are solved .

I wonder how many problems over the years have been based on this "knapsack" recurrence. A7 from 2010 comes to mind - and the post on that references C4 from 2009. Anybody knows any other examples?

Note that, if $i>j>2017$, then we have $a_i+a_j\le a_j-(a_j+a_{i-j})=-a_{i-j}$. So, for all $n>4034$, we have that $$a_n=-\max_{i+j=n}(a_i+a_j)\ge\min_{i+j=n}a_{|j-i|}$$So, every new number in the sequence can't be less than all the previous ones of the same parity, and therefore the sequence $a_n$ is bounded from below. Of course, this means that $a_i+a_j$ is bounded from below, so $a_n$ must also be bounded from above as well.

interesting

The logic of this solution is a bit weird, but I think it works. Suppose for the sake of contradiction that $(a_i)$ is not bounded. This means that there is some $n>2017$ such that \[D:=|a_n|>|a_1|,\ldots,|a_{n-1}|.\]Funnily enough, we'll show that this condition implies that $(a_i)$ must be bounded, which is a contradiction. But first we need a lemma. Case 1: $a_n>0$. Note that \[\max_{i\in[n-1]}(a_i+a_{n-i})=-D,\]so $a_i+a_{n-i}\le -D$. But $|a_{n-i}|<D$, so $-a_{n-i}<D$. Thus, \[a_i\le -D-a_{n-i}<-D+D=0,\]so $a_1,\ldots,a_{n-1}<0$. We now have the following claim. Claim 1: We have \[-2D\le a_m\le D\]for all $m$. Proof of Claim 1: We proceed by induction on $m$. For $m=1,\ldots,n$, the statement is clearly true. Now suppose \[-2D\le a_{m'}\le D\]for all $m'<m$ where $m>n$. Note that \[\max_{i\in[m-1]}(a_i+a_{m-i})\le D+D=2D,\]so $a_m\ge -2D$. Also note that $a_n+a_{m-n}\ge D-2D\ge -D$, so \[\max_{i\in[m-1]}(a_i+a_{m-i})\ge -D,\]so $a_m\le D$, as desired. This completes the induction. $\blacksquare$ Thus, $(a_i)$ is bounded, which is a contradiction. Case 2: $a_n<0$. We see that \[D=\max_{i\in[n-1]}(a_i+a_{n-i}).\]Let $A=\max_{i\in[n-1]} a_i$. Note that $D\le 2A$, so $a_i>-D\ge -2A$ if $i\in[n-1]$. Thus, we have \[-2A\le a_i\le A\]for all $i\in[n-1]$. Let $j\in[n-1]$ so that $a_j=A$. We now have a very similar claim as claim 1. Claim 2: We have \[-2A\le a_m\le A\]for all $m$. Proof of Claim 2: We proceed by induction on $m$. We essentially showed above that the claim holds for $m=1,\ldots,n-1$. Now suppose \[-2A\le a_{m'}\le A\]for all $m'<m$ where $m\ge n$. Note that \[\max_{i\in[m-1]}(a_i+a_{m-i})\le A+A=2A,\]so $a_m\ge -2A$. Also note that $a_j+a_{m-j}\ge A-2A\ge -A$, so \[\max_{i\in[m-1]}(a_i+a_{m-i})\ge -A,\]so $a_m\le A$, as desired. This completes the induction. $\blacksquare$ Thus, $(a_i)$ is bounded, which is a contradiction. Thus, $(a_i)$ is bounded. $\blacksquare$

math90 wrote: A sequence of real numbers $a_1,a_2,\ldots$ satisfies the relation $$a_n=-\max_{i+j=n}(a_i+a_j)\qquad\text{for all}\quad n>2017.$$Prove that the sequence is bounded, i.e., there is a constant $M$ such that $|a_n|\leq M$ for all positive integers $n$. Solution: From the condition of the problem note that it is enough to show that the sequence is bounded above by some $M$ as then we naturally get the lower bound $-2M$ Assume for the sake of contradiction that $<a_n>$ is not bounded above. Also note that one of $a_1,a_2,\cdots,a_{2018}$ must be non-negetive . Now define a subsequence as follows - 1. $a_{b_1}$ is the first non-negetive term 2. Let $a_{b_n}$ be the first term after $a_{b_{n-1}}$ which is strictly greater than it. Claim 1- For $2017<i<b_{n+1}$ we have $a_i\geq -2a_{b_n}$ Proof- Note that $a_i=-(a_t+a_{t-i})$ for some $t$ . But from definition of $b_{n+1}$ we have $a_t,a_{i-t}\leq a_{b_n} \implies a_i\geq -2a_{b_n}$ Claim 2- For $b_n>2017 , b_{n+1}-b_n\leq 2017$ Proof- If possible let $x=b_{n+1}-b_n$ be greater than $2017$ Then by claim 1 we have $a_x\geq -2a_{b_n} \implies a_{b_n}+a_x \geq -a_{b_n} $ But $-a_{b_n}>-a_{b_{n+1}}\geq a_x+a_{b_n}\geq -a_{b_n}$ Contradiction and hence claim is proved Now we will use this claim to show that $a_{b_n}$ is bounded and hence get a contradiction. Let $K=min\{a_1,a_2,\cdots,a_{2017}\}$ Then we have $-a_{b_{n}}\geq a_{b_{n-1}}+a_{b_{n}-b_{n-1}}\geq a_{b_{n-1}}+K \geq K \implies a_{b_n}\leq -K$ Contradiction !!!! Hence proved.

Nice problem. Suppose that this sequence is bounded from below, then $a_i > M$ for all $i \in \mathbb{N}$. This gives us for sufficiently large $n$, \[ a_n = -\max_{i + j = n} (a_i + a_j) < -2M \]which means that the sequence is bounded. We'll now prove that this sequence is bounded from below. Notice that \[ a_{i + k} = -\max_{\ell + m = i + k} (a_{\ell} + a_{m} ) \le -(a_i + a_k) \]for all large $i$ and $k$. Therefore $a_{i + k} + a_i \le a_k$. \[ a_{\ell + m} = -\max_{\ell > m} (a_{\ell} + a_{m} ) \ge \min a_{\ell - m} \]This shows that the term $V_k = \min \{ a_1, a_2, \dots, a_k \}$ will stay the same when $k$ grows arbitrarily large. Proving that this sequence is bounded from below.

a bit easy for A4 but a nice one here's my solution: let $a_m=Max\{a_1,a_2,.\dots ,a_{2\times 2017}\}$ claim(1): $a_m \ge a_i \forall i \in \mathbb{N}$ proof: suppose the smallest $j$ such that $a_j >a_m$ clearly $j>2\times 2017$ $$-(a{j-m}+a_m) \ge a_j >a_m$$so $$2a_s\ge a_s+a_t=-a_{j-m}>2a_m$$so $a_s>a_m$ but $s<j$ a contradiction $\blacksquare$ claim(2): $a_i \ge -2a_m \forall i \in \mathbb{N}$ proof: suppose there's $j$ such that $a_j<-2a_m$ but $$a_j=-a_s-a_t<-2a_m$$so $a_s+a_t>2a_m$ but from claim(1) we have $a_s,a_t \le a_m$ so $$2a_m\ge a_s+a_t > 2a_m$$$\blacksquare$ and we win

Let $a_n\geq 0$ and $|a_n|>|a_i|$ for all $i<n$. Then $a_i+a_{n-i}\leq 0$ for all $i<n$, so at least one of each pair is non-positive. But if $a_i$ and $a_{n-i}$ are of opposite sign, we have $|a_n|\leq |a_i+a_{n-i}|<\max\{|a_i|,|a_{n-i}|\}$, a contradiction. So we have that all of $a_1,a_2,...,a_{n-1}$ are negative, which can obviously happen at most once. So there is some $M$ with $a_n<M$ if $a_n\geq 0$ Now suppose $a_n<0$, and $a_k+a_{n-k}=\max_{i<n}(a_i+a_{n-i})$. Again, if $a_k$ and $a_{n-k}$ are of opposite sign, $|a_n|$ is less then some $|a_i|,i<n$. If they are of the same sign, they are both positive, meaning $|a_n|=|a_k+a_{n-k}|=|a_k|+|a_{n-k}|<2M$ $\blacksquare$

Suppose on the contrary that the sequence is unbounded, then CLAIM . The positive and negative terms of the sequence is unbounded Proof. Suppose the positive terms is bounded, let its maximum value be $M$, then for every $i,j$ we have $a_i+a_j<2M$, hence $$a_n=-\max_{i+j=n}(a_i+a_j)>-2M$$hence the sequence is bounded, contradiction. Now let $a_{p_1}<a_{p_2}<...$ be an unbounded subsequence of positive terms (we pick these terms so that for each $p_i$ we have $a_{p_{i}}=\max\{a_k|1\leq k\leq p_i\})$, then we have $$a_{p_m+p_{m+1}}=-\max_{i+j=p_m+p_{m+1}}(a_i+a_j)<-(a_{p_m}+a_{p_{m+1}})$$hence it is unbounded $\blacksquare$ Now take a sufficiently large $k$ and consider $a_{p_k}$. Let $a_m$ be the smallest integer among $a_1,a_2,...,a_{p_k-1}$, obviously it is negative. We take $k$ sufficiently large such that $m>2017$. Now notice that $$a_{p_k}=-\max_{i+j=k}(a_{i}+a_j)\leq -(a_{p_{k-1}}+a_{p_k-p_{k-1}})$$Hence $$a_{p_k}+a_{p_k-1}\leq -a_{p_k-p_{k-1}}\leq -a_{m} \qquad (1)$$However, since $2017<m<p_i$, we have $$-a_m=\max_{i+j=m}(a_i+a_j)<a_{p_i-1}+a_{p_i} \qquad (2)$$from the maximality of $p_i-1$ and $p_i$. We put together $(1)$ and $(2)$ to obtain a contradiction, the proof is thus completed.

Solved with nukelauncher and Th3Numb3rThr33. Observe that it suffices to bound the sequence from above; if we bound \(a_n\le M\), then the sequence is always at least \(-2M\). Call \(n\) a peak if \(a_n>\max\{a_1,\ldots,a_{k-1}\}\); Assume for contradiction the sequence is unbounded above, so there are infinitely many peaks. Indeed, for large \(2017\ll k<\ell\), if \(k\) and \(\ell\) are consecutive peaks, then \(a_k+a_{\ell-k}<-a_\ell<-a_k\), so \(a_{\ell-k}<-2a_k\). Assume \(\ell-k>2017\). This means that for some \(i\), we have \(a_i+a_{\ell-k-i}>2a_k\); without loss of generality \(a_i\ge a_{\ell-k-i}\), so \(a_i>a_k\). But this is a contradiction, since if \(i<k\), then \(k\) would not be a peak; and if \(k<i<\ell\), then \(k\) and \(\ell\) would not be consecutive peaks. Hence \(\ell-k\le2017\). But then for all peaks \(k\), we have \(a_k<\frac12a_{\ell-k}\), which is bounded above since \(a_{\ell-k}\) takes finitely many values.

Such beautiful solutions

First initially consider the first $N$ terms for $N$ sufficiently large such that $a_1, a_2, \dots, a_N$ has both negative and positive terms, which clearly must occur. Let $0<M = \max\{a_1, a_2, \dots, a_N\}.$ Claim: All subsequent terms are bounded above by $M$. Proof. We prove this by induction, by assumption $n=N$ is our base case and is true. Assume it is true for the first $n$ terms, so it then suffices to show $a_{n+1} \le M.$ Note that all terms are bounded below by $-2M.$ Hence, suppose for the sake of contradiction $a_{n+1} > M,$ implying that for all $i+j = n+1,$ $$-2M\le a_{n+1} = a_i + a_j < - M$$However, by assumption, there exists some $k$ such that $a_k = M,$ giving a clear contradiction as then $$a_k + a_{n+1 - k} \ge -2M + M = -M,$$Completing the induction step and therefore concluding all terms are bounded above. $\blacksquare$ Evidently then, all terms are also bounded below by $-2M,$ so we're done.

math90 wrote: A sequence of real numbers $a_1,a_2,\ldots$ satisfies the relation $$a_n=-\max_{i+j=n}(a_i+a_j)\qquad\text{for all}\quad n>2017.$$Prove that the sequence is bounded, i.e., there is a constant $M$ such that $|a_n|\leq M$ for all positive integers $n$. Time to add my solution: We observe that if $i > j > 2017$, then $a_i + a_j = a_j -\max_{m+n=i}(a_m+a_n) \leq a_j - (a_j + a_{i-j}) = -a_{i-j} \implies a_n \geq \text{min}_{i+j=n} a_{i-j}$ for all sufficiently large enough $n$. This means that $a_n$ is bounded below. This means that $-a_n = \text{max}_{i+j=n} a_i + a_j$ is bounded from above, implying that $a_i + a_j$ is bounded from above for all indices $i, j$, implying that $a_i$ is bounded above for all indices $i$ as desired.

I did a bunch of complicated stuff before realizing that simple stuff actually just works . Cute problem. Among the first $2021$ terms, let $A$ be the maximum value and let $-B$ be the minimum value among them. Observe that any term that appears next must be at most $-(A-B) = B-A$ since there will be some pair of $i,j$ containing the $a_i = A$. If $B-A \le A$, this means the sequence is upper bounded by $A$. If not, then we have $B-A > A$ as our new maximum. Now, terms after this can be at most $B-(B-A) = A$ which is $< B-A$, so the sequence is again upper bounded by $B-A$. So if it is upper bounded, say by $N$, then any term must be at least $-2N$, so it is lower bounded too. Therefore, the sequence is bounded, as desired. $\blacksquare$

Claim1: If $\max_{1\leq i\leq n}(a_i)=a_k\geq 0$ and $\min_{1\leq i\leq n}(a_i)\geq-2a_k$, then $-2a_k\leq a_{n+1}\leq a_k$. Proof $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)\leq-a_k-a_{n+1-k}\leq-a_k-(-2a_k)=a_k$ $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)\geq-(a_k+a_k)=-2a_k$ $\therefore$ Claim1 holds. Claim2: If $\min_{1\leq i\leq n}(a_i)=a_l<0$ and $\max_{1\leq i\leq n}(a_i)<-\frac{a_l}{2}$, then $\forall m\geq n+1,\; 4a_l\leq a_m\leq -2a_l$. Proof $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)\leq-(a_l+a_l)\leq-2a_l$. $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)>-(-\frac{a_l}{2}-\frac{a_l}{2})=a_l$. If $a_{n+1}\geq-\frac{a_l}{2}$, then by induction on $m$ with Claim1, $\forall m\geq n+1,\; -2a_{n+1}\leq a_m\leq a_{n+1}$. If $a_{n+1}<-\frac{a_l}{2}$, then by induction on $m$ with Claim2, $\forall m\geq n+1,\; -2a_{n+1}\leq a_m\leq a_{n+1}$. $\therefore$ Claim2 holds. $\because\{a_i\}$ satisfies either the condition of Claim1 or Claim2. $\therefore$ the sequence is bounded.

L567 wrote: I did a bunch of complicated stuff before realizing that simple stuff actually just works . Cute problem. Among the first $2021$ terms, let $A$ be the maximum value and let $-B$ be the minimum value among them. Observe that any term that appears next must be at most $-(A-B) = B-A$ since there will be some pair of $i,j$ containing the $a_i = A$. If $B-A \le A$, this means the sequence is upper bounded by $A$. If not, then we have $B-A > A$ as our new maximum. Now, terms after this can be at most $B-(B-A) = A$ which is $< B-A$, so the sequence is again upper bounded by $B-A$. So if it is upper bounded, say by $N$, then any term must be at least $-2N$, so it is lower bounded too. Therefore, the sequence is bounded, as desired. $\blacksquare$ If the next term doesn't increase the maximum it can decrease the minimum and therefore making your bound of $B-(B-A)=A$ incorrect.

gvole wrote: If the next term doesn't increase the maximum it can decrease the minimum and therefore making your bound of $B-(B-A)=A$ incorrect. Right, I should have specified, that the new number is at least $-(-B+(B-A)) = -A > -B$ so the minimum may never decrease.

Ali3085 wrote: a bit easy for A4 but a nice one here's my solution: let $a_m=Max\{a_1,a_2,.\dots ,a_{2\times 2017}\}$ claim(1): $a_m \ge a_i \forall i \in \mathbb{N}$ proof: suppose the smallest $j$ such that $a_j >a_m$ clearly $j>2\times 2017$ $$-(a{j-m}+a_m) \ge a_j >a_m$$so $$2a_s\ge a_s+a_t=-a_{j-m}>2a_m$$so $a_s>a_m$ but $s<j$ a contradiction $\blacksquare$ claim(2): $a_i \ge -2a_m \forall i \in \mathbb{N}$ proof: suppose there's $j$ such that $a_j<-2a_m$ but $$a_j=-a_s-a_t<-2a_m$$so $a_s+a_t>2a_m$ but from claim(1) we have $a_s,a_t \le a_m$ so $$2a_m\ge a_s+a_t > 2a_m$$$\blacksquare$ and we win You don't know that $j-m>2017$.

L567 wrote: gvole wrote: If the next term doesn't increase the maximum it can decrease the minimum and therefore making your bound of $B-(B-A)=A$ incorrect. Right, I should have specified, that the new number is at least $-(-B+(B-A)) = -A > -B$ so the minimum may never decrease. The next term being at least $-(-B+(B-A)) = A$ implies the sequence is increasing. You must've made a mistake somewhere.

Oops, this is what happens when I'm not using my brain. I meant to write instead, since $A$ is the maximum number, for minimum value of the next term, we must have $a_i + a_j$ maximized, but this is at most $2A$ so the next term is at least $-2A > -B$ since we assumed $B-A > A$.

sn6dh wrote: Claim1: If $\max_{1\leq i\leq n}(a_i)=a_k\geq 0$ and $\min_{1\leq i\leq n}(a_i)\geq-2a_k$, then $-2a_k\leq a_{n+1}\leq a_k$. Proof $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)\leq-a_k-a_{n+1-k}\leq-a_k-(-2a_k)=a_k$ $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)\geq-(a_k+a_k)=-2a_k$ $\therefore$ Claim1 holds. Claim2: If $\min_{1\leq i\leq n}(a_i)=a_l<0$ and $\max_{1\leq i\leq n}(a_i)<-\frac{a_l}{2}$, then $\forall m\geq n+1,\; 4a_l\leq a_m\leq -2a_l$. Proof $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)\leq-(a_l+a_l)\leq-2a_l$. $a_{n+1}=-\max_{i+j=n+1}(a_i+a_j)>-(-\frac{a_l}{2}-\frac{a_l}{2})=a_l$. If $a_{n+1}\geq-\frac{a_l}{2}$, then by induction on $m$ with Claim1, $\forall m\geq n+1,\; -2a_{n+1}\leq a_m\leq a_{n+1}$. If $a_{n+1}<-\frac{a_l}{2}$, then by induction on $m$ with Claim2, $\forall m\geq n+1,\; -2a_{n+1}\leq a_m\leq a_{n+1}$. $\therefore$ Claim2 holds. $\because\{a_i\}$ satisfies either the condition of Claim1 or Claim2. $\therefore$ the sequence is bounded. In claim 2 you can decrease the minimum, which increases your upper bound and decreases your lower bound.

L567 wrote: Oops, this is what happens when I'm not using my brain. I meant to write instead, since $A$ is the maximum number, for minimum value of the next term, we must have $a_i + a_j$ maximized, but this is at most $2A$ so the next term is at least $-2A > -B$ since we assumed $B-A > A$. You showed the next terms must be at most $B-A$ and the part where you say they are at most $A$ relies on the existence of a term $B-A$ which doesn't have to exist so your maximum can be something between $A$ and $B-A$.

Why doesn’t this work? Suppose there exists a monotonic infinite sequence. It is clear that a strictly increasing infinite sequence exists iff a strictly decreasing infinite sequence exists. So assume that an arbitrary small negative number $a_n$ is in the sequence such that $a_n < min(a_1,a_2,…a_{n-1})$ Then $a_n = -(a_i + a_{n-i})$ where $i > n-i$ WLOG. Then $a_i \leq -( a_{n-i}+a_{2i-n}) \implies a_{2i-n} \leq a_n$ which is a contradiction due to the previous assumption. Hence we are done.

Suppose otherwise, so $(a_n)$ is unbounded above since if it's bounded above it's also bounded below. Thus we can pick $k>2017$ such that $a_i \geq -2a_k\forall i \leq 2017$ and $a_i \leq a_k\forall i<k$, in which case $-2a_k\leq a_i \leq a_k$ for all $i \leq k$. But then by strong induction $-2a_k \leq a_i \leq a_k$ for all $i>k$ as well, so $(a_n)$ is bounded—contradiction. $\blacksquare$ Relevant details which were left out to create an artificially short solution: If $a_i \leq M$ for all $i$, then $a_i \geq -2M$ for all $i>2017$, so $(a_n)$ bounded above implies that it's bounded below as well. After picking $k$, we have $a_i \geq -2a_k$ for all $2017<i \leq k$ since for such $i$, we have for some $j<i$ that $a_i=-(a_j+a_{i-j})\geq -2a_k$, since $a_j,a_{i-j}\leq a_k$. For the strong induction, note that if $-2a_k \leq a_i \leq a_k$ for all $i<N$, where $N>k$, we have $$a_N\geq -(a_k+a_k)=-2ak \text{ and } a_N \leq -(a_k+a_{N-k}) \leq -(a_k-2a_k)=a_k,$$so $-2a_k\leq a_N \leq a_k$ as well.

william122 wrote: Note that, if $i>j>2017$, then we have $a_i+a_j\le a_j-(a_j+a_{i-j})=-a_{i-j}$. So, for all $n>4034$, we have that $$a_n=-\max_{i+j=n}(a_i+a_j)\ge\min_{i+j=n}a_{|j-i|}$$So, every new number in the sequence can't be less than all the previous ones of the same parity, and therefore the sequence $a_n$ is bounded from below. Of course, this means that $a_i+a_j$ is bounded from below, so $a_n$ must also be bounded from above as well. I think this solution is wrong (and for example #18, #30) because it is possible to have $i=j$ for even $n$. #2 uses the same idea but applies it for odd $n$.

I will prove a more general variation, in which $n > k$ instead of $n > 2017$ where $k$ is a finite positive integer. let ${(b_n)}_{n \in \mathbb{N}}$ be a sequence of positive numbers such that $b_1$ is the first positive number among $a_1$, $a_2$, ... $b_2$ a second positive number among the same sequence, and so on. We will prove that the sequence ${(b_n)}_{n \in \mathbb{N}}$ is bounded (i.e. it has a maximal element). we may assume that ${(b_n)}_{n \in \mathbb{N}}$ is infinite and that for any $i \in \mathbb{N}$ there exists $j \in \mathbb{N}$ such that: $b_i < b_j$ for the sake of contradiction. claim 1. there are infitely many numbers $l \in \mathbb{N}$ such that $b_l > b_1, b_2, ..., b_{l-1}$ proof: define another sequence ${(c_n)}_{n \in \mathbb{N}}$ by $c_1 = b_1$ and $c_n$ being the first number in ${(b_n)}_{n \in \mathbb{N}}$ greater than $c_{n-1}$ there will always exist such a number because, for every number in ${(b_n)}_{n \in \mathbb{N}}$ there exists a greater number and ${(c_n)}_{n \in \mathbb{N}}$ is infinite as well. notice that $c_n$ is greater than all numbers that appear before him in the sequence ${(b_n)}_{n \in \mathbb{N}}$ for every $n$ and we are done with the proof. now let's choose an arbitrarily large such $k \in \mathbb{N}$, then there exists $l \in \mathbb{N}$ such that $a_l = b_k$ claim: $a_x = -\max(a_i + a_{x-i}) \le -(a_{x-l} + a_l) \le a_l$ for all $x \in \{ k+l+1, k+l+2, ..., 2l-1 \}$ proof: since $2l > x > k + l \Leftrightarrow l > x-l > k$ then: $a_{x-l} = -(a_y + a_{x-l-y})$ and $y<x-l, x-l-y<x-l$ so $a_y \le a_l$ and $a_{x-l-y} \le a_l$ WLOG $a_y \geq a_{x-l-y}$ then: $2a_l \geq 2a_y \geq a_y + a_{x-l-y} = -a_{x-l} \Leftrightarrow a_l \geq -a_{x-l} -a_l = -(a_{x-l}+a_l) \geq -\max(a_i + a_{x-i}) = a_x$ and thus $a_l \geq a_x$ for all $x \in \{ k+l+1, k+l+2, ..., 2l-1 \}$. Now let $M=a_m = \max(\{a_l, a_{l+1}, ..., a_{k+l}\})$ claim: there does not exist a number in the sequence strictly greater than $M$. proof (using strong induction): Base: $a_1, a_2, ..., a_{2l-1} < a_m=M$ Step: we claim that $a_{n+1} = -\max(a_i + a_{n+1-i}) \le -(a_m + a_{n+1-m}) \le a_m$ proof: $n+1-m \geq 2l-(k+l) = l-k > k$ for a large enough $l$ and thus $a_{n+1-m} = a_u + a_{n+1-m-u}$ and by induction hypothesis $a_m \geq a_u$ and $a_m \geq a_{n+1-m-u}$. WLOG $a_u \geq a_{n+1-m-u}$. then $2a_m \geq 2a_u \geq a_u + a_{n+1-m-u} = -a_{n+1-m} \implies 2a_m \geq -a_{n+1-m} \Leftrightarrow a_m \geq -(a_{n+1-m} + a_m) \geq -\max(a_i + a_{n+1-i})=a_{n+1}$ and we are done. but this contradicts the original assumption and ${(b_n)}_{n \in \mathbb{N}}$ must be bounded. It only remains to show that all of the negative numbers are bounded as well indeed: $a_n = -\max(a_i + a_{n-i}) \geq -(M+M) = -2M$ and we are done.

Let $M_n=\max(a_1,a_2,\dots,a_n), m_n = \min(a_1,a_2,\dots,a_n)$. Case 1: $m_n \geq -2M_n$ for some $n \ge 2017$. Then I claim $a_k \in [-2M_n,M_n]$ for all $k$. Use induction on $k$. Indeed, for $k \le n$ this is true, and subsequently, \[M_n = -(-2M_n+M_n) \ge -(a_l +a_{k-l}) \ge a_k \ge -(M_n+M_n) = -2M_n \]where $l$ is some index for which $a_l=M_n$. This proves the claim. Case 2: $m_n < -2M_n$ for all $n \ge 2017$. Then I claim $a_k \in [m_{2017},-\frac{m_{2017}}{2}]$ for all $k$. Again, we show this by induction. This is true for $k=2017$,and for $k>2017$, \[\frac{m_{2017}}{2} \ge M_{k-1} \ge a_k \ge -2M_{k-1} \ge m_{2017}\]so the sequence is bounded once again

Assume it is unbounded from above. Call $n>2017$ good if $a_n>\max(a_1,a_2,\dots,a_{n-1})$. Since it is unbounded, there are infinitely many good numbers. If $n$ and $n+d$ with $d>0$ are good such that there are no good numbers in between, then \[a_n<a_{n+d}\le -(a_n+a_d)\]so $-a_d>2a_n$. If $d>2017$, then for some $e<d$, $a_e+a_{d-e}=-a_d$. Since $d<n+d$, and between $n$ and $n+d$ no numbers are good, we must have $a_e+a_{d-e}\le 2a_n$, which is a contradiction. Thus, $d\le 2017$ between any two adjacent good numbers. However, this means that for all good $n$, $a_n\le -\tfrac{a_d}{2}$ for some $d$, but that's also a contradiction to unboundedness. Now, since it is bounded from above, let $a_n\le X$ for all $n$. Then, for all $q>2017$, $a_q\ge -2X$. Thus, it is bounded.

math90 wrote: A sequence of real numbers $a_1,a_2,\ldots$ satisfies the relation $$a_n=-\max_{i+j=n}(a_i+a_j)\qquad\text{for all}\quad n>2017.$$Prove that the sequence is bounded, i.e., there is a constant $M$ such that $|a_n|\leq M$ for all positive integers $n$. Let $M=\max(a_i)$ and $m=\min(a_i)$ for some $i \geq N $ where $N$ is a sufficiently large integer. We want to show that for all integers $s \geq N$ we have that $m \leq a_s \leq M$. Note that since $M$ is maximum then. $a_k = - \max_{i\in k-1}(a_i+a_k-i)\geq -(M+M) = -2M$. Meaning that $a_k \geq -2M $ for all $k\leq N$. so proving that the sequence is bounded from above solves the problem. We will prove that by induction. Now assume for the sake of contradiction that $a_{N+1} > M$. But since $a_{N+1}=-\max(a_i+a_{N-i+1})\geq M-2M = -D $ Implying that $a_{N+1} \leq M$ a contradiction! So by induction we are done

Let $M_n$ be the maximum of the first $n$ terms and $-m_n$ be the largest and smallest elements in the set $\{a_1, a_2, \ldots, a_n\}$. Then, for any $n$, we have \[-2M_n\leq a_{n+1}\leq m_n-M_n\]We now consider two cases. Case 1. $2M_n\geq m_n$. Suppose $a_k=M_n$ is the smallest such $k\leq n$. Then, $a_{2k}=-2M_n\leq-m_n$, which means $2k\geq n$ and $m_{2k}=2M_n$. We show that $M_{2k}=M_n$. Suppose not. Note that for any $n<i\leq 2k$, if $a_i>M_n$ then $-M_n> -a_i\geq a_k+a_{i-k}=M_n+a_{i-k}\Longrightarrow a_{i-k}< -2M_n\leq -m_n$, which is impossible as $i-k\leq n$. Hence, $M_{2k}=M_n$ and $m_{2k}=2M_n$. Note that $-m_{2k}=-2M_n\leq a_{2k+1}\leq m_{2k}-M_{2k}=M_n$, which means $m_{2k+1}=m_{2k}=-2M_n$ and $M_{2k+1}=M_{2k}=M_n$. A simple induction gives that for any $j>0$, we have $M_{2k+j}=M_{2k}=M_n$ and $m_{2k+j}=m_{2k}=-2M_n$. Hence, the sequence is bounded above by $M_n$ and below by $-2M_n$, which means it is bounded. $\blacksquare$ Case 2. $2M_n<m_n$. Let $k_1, k_2\leq n$ be indices for which $a_{k_1}=M_n$ and $a_{k_2}=m_n$. Also, suppose that $a_{k_1+k_2}\geq m_n-M_n>M_n$. Note that $a_{2k_1}\geq-2M_n>-m_n$. Let $k=\max\{k_1+k_2,2k_1\}$. Then, $M_k>M_n$ and $m_k\leq2M_k$. This is similar to Case 1 done above. $\blacksquare$ The proof is complete. $\blacksquare$ Remark. The problem may be generalized to \[a_n=-\max_{i_1+i_2+\cdots+i_k=n}(a_{i_1}+a_{i_2}+\cdots+a_{i_k})\qquad\text{for all}\quad n>D\]being a bounded sequence.

Call $a_n$ locally big, if for all $i < n$ inequality $a_i \leq a_n$ holds. Lemma 1: if $a_n>0$ is locally big, and all negative numbers $a_i$ for $i < n$ are at least $-2a_n$, we are done. Proof: I will prove by induction that all elements of the sequence lie in the range $[-2a_n,a_n]$. Obviously it is true for all elements $a_1,\ldots,a_n$. Now suppose it is true till $a_k$. Then $a_{k+1} \leq -(a_n+a_{k+1-n}) \leq -(a_n-2a_n)=a_n$ and $a_{k+1}=-(a_i+a_{k+1-i}) \geq -a_n-a_n=-2a_n$ Clearly, all elements are bounded now Call $a_n$ modulo-big, if for all $i<n$ inequality $|a_i| \leq |a_n|$ holds. Clearly, Lemma 1 applies to all modulo-big positive elements. FTSOC suppose there is an unbounded sequence for which conditions from problem statement hold. Then there are infinitely many modulo-big elements, and all of them are negative. Take any, say $a_n<0$, and let the next one be $a_m<a_n$. Then there is a positive number $a_k$, where $k<m$, such that $a_k \geq \frac{|a_m|}{2}$. But then Lemma 1 applies to it.

Solved with Brudder. Assume that it is not bounded. Note that if it is bounded above, then $a_i,a_j<c$, so the max is $<2c$, so $a_n>-2c$ for large enough $n$, so $a$ is also bounded below. So now take a sufficiently large new prefix max, say $a_n=k$. Clearly nothing before $a_n$ could have been $<-2k$ (something $>k$ couldn't have been one of the first $2017$). So then the first $n$ elements are in $[-2k,k]$, and $k$ actually appears. Now induction works: the max is at most $2k$ so each element is at least $-2k$, and for each $n$ we can always pick the one with $k$ to get the max is at least $-k$ so each element is at most $k$. $\blacksquare$