What a disappointing #6

Let $t=max\{\frac {a_1}1, \frac {a_2}2, \ldots, \frac {a_s}s\}$ and let $S=\{i\mid \frac {a_i}{i}=t\}$, and choose $\ell \in S$. It is immediate by induction that $a_n\leq nt$ for all $n$. Consider now the sequence $b_n=nt-a_n$ and let's look at the $\ell$ subsequences $b_i, b_{i+\ell}, b_{i+2\ell}, \ldots$ formed by arithmetic progressions of difference $\ell$. These subsequences are (eventually) non-increasing because $a_{n+\ell}\geq a_n+a_\ell$ for $n\geq s$. On the other hand, they also take finitely many values. Indeed, each $a_n$ can be written as a sum $a_{i_1}+\ldots+a_{i_r}$ for $i_1, \ldots, i_r\in \{1, \ldots, s\}$ with $i_1+i_2+\ldots+i_r=n$ which implies $b_n=b_{i_1}+\ldots+b_{i_r}$. The quantities $b_{i_k}$ are either zero (if $i_k\in S$) or take one of the finitely many possible non-zero values in $\{b_1, \ldots, b_s\}$. In any case, since their sum is bounded (because $b_{i+m\ell}$ is eventually non-increasing in $m$), there are only finite many values for this sum (for example, we can bound the number of the occurences of each $j\not \in S$ as one of the $i_k$ by $\frac {C}{b_j}$ where $C$ is a positive constant such that $b_n\leq C$ - and we do not care for $j\in S$). Thus, each subsequence $b_i, b_{i+\ell}, b_{i+2\ell}$ is non-increasing but can only contain a finite number of distinct terms so it eventually stabilizes meaning $a_{i+(n+1)\ell}=a_{i+n\ell}+a_{\ell}$ for all sufficiently big $n$. Taking $i$ covering all residues modulo $n$ the conclusion follows.

Hm... A slightly more constructive approach: Let $a_{n} = a_{x_1} + a_{x_2} + ... + a_{x_k}$, with $\sum {x_i} = n$. If $n$ is too large, some of the indices (wich are assumed to be $< s$) is going to appear at least $\ell$ times. It is easy to see that, e.g., $a_{x_1 + x_3 + x_8} = a_{x_1} + a_{x_3} + a_{x_8}$, for $a_{x_1 + x_3 + x_8} \ge a_{x_1 + x_3} + a_{x_8} \ge a_{x_1} + a_{x_3} + a_{x_8}$ and, if the left side were greater, we would have a better bound for $a_n$. Now, say we have $x_1 = x_2 = ... = x_{\ell} = t$. Then $a_{n - t\ell} = a_{n - x_1 - ... - x_{\ell}} = a_n - \ell a_t \ge a_n - ta_{\ell}$. Thus $a_{n - \ell} \ge a_{n - t\ell} + a_{\ell} + ... + a_{\ell} = a_{n - t\ell} + (t - 1)a_{\ell} \ge a_n - a_{\ell}$. The reverse inequality is obvious.

Let $l$ be an integer, $1 \leq l \leq s$, which maximizes $\frac{a_l}{l}$. Then, we have the following result: $\frac{a_n}{n} \leq \frac{a_l}{l}$ by induction on $n$. Now, consider, for a fixed $k>s$, the sequence $b_n = a_l(k+nl) - a_{k+nl}l$. We have $b_n=a_l(k+nl) - a_{k+nl}l \leq a_l(k+nl) - (a_{k+(n-1)l}+a_l)l = b_{n-1}$. Therefore, the sequence is (weakly) decreasing. Since it only contains nonnegative integers, it must be eventually constant. This means that the sequence $c_n = a_ln - a_{n}l$ must eventually only depend on the value of the residue of $n \pmod l$, which implies the result.

So, during the US training camp this year, we did ISL 2009 C4 on one of our mock IMOs. If you do that problem, you get a recursion similar to this and the answer is of the form: n+a if n even n+b if n odd a,b are constants. This motivates the idea of subtracting kn from a_n for all n, and then you choose k so that, after subtracting, at least one of the first s numbers is 0 and none of the first s numbers are positive. Doing this is essentially maximizing a_k/k like the other solutions did. I think this problem is extremely easy if you have seen a sequence satisfying that kind of recursion before, so it's pretty stupid to put this problem on the IMO after the ISL is released and problem C4 uses this kind of recursion. Though I guess it doesn't matter since you can just mess around a bit with the problem and then realize the above. The US did C4 on a Mock IMO, so i hope US can do well this year at imo

well ,this problem 6 is a bit easy I think...I hope my solution is correct. We fix a $N>2s$ if there exist a $n\geqslant N$ and $a_n=a_m+a_{n-m}$ where $n-m>m>s$ ,we can find out a integer $k$ which is not larger than $\frac{m}{2}$ and $a_m=a_k+a_{m-k}$ .It indicates that $a_n=a_k+a_{m-k}+a_{n-m}$.Because $n-m>s$,we attain that $a_{m-k}+a_{n-m}\leqslant a_{n-k}$ and $a_n=a_k+a_{n-k}$(or it will contradict) if $k\leqslant s$ we settle the problem or we can go on to do the same operation until we get it.

iura wrote: Let $t=max\{\frac {a_1}1, \frac {a_2}2, \ldots, \frac {a_s}s\}$ and let $S=\{i\mid \frac {a_i}{i}=t\}$, and choose $\ell \in S$. It is immediate by induction that $a_n\leq nt$ for all $n$. Consider now the sequence $b_n=nt-a_n$ and let's look at the $\ell$ subsequences $b_i, b_{i+\ell}, b_{i+2\ell}, \ldots$ formed by arithmetic progressions of difference $\ell$. These subsequences are (eventually) non-increasing because $a_{n+\ell}\geq a_n+a_\ell$ for $n\geq s$. On the other hand, they also take finitely many values. Indeed, each $a_n$ can be written as a sum $a_{i_1}+\ldots+a_{i_r}$ for $i_1, \ldots, i_r\in \{1, \ldots, s\}$ with $i_1+i_2+\ldots+i_r=n$ which implies $b_n=b_{i_1}+\ldots+b_{i_r}$. The quantities $b_{i_k}$ are either zero (if $i_k\in S$) or take one of the finitely many possible non-zero values in $\{b_1, \ldots, b_s\}$. In any case, since their sum is bounded (because $b_{i+m\ell}$ is eventually non-increasing in $m$), there are only finite many values for this sum (for example, we can bound the number of the occurences of each $j\not \in S$ as one of the $i_k$ by $\frac {C}{b_j}$ where $C$ is a positive constant such that $b_n\leq C$ - and we do not care for $j\in S$). Thus, each subsequence $b_i, b_{i+\ell}, b_{i+2\ell}$ is non-increasing but can only contain a finite number of distinct terms so it eventually stabilizes meaning $a_{i+(n+1)\ell}=a_{i+n\ell}+a_{\ell}$ for all sufficiently big $n$. Taking $i$ covering all residues modulo $n$ the conclusion follows. I think t should be the smallest

Please someone help me! I've thought a lot about this problem and I've read all the solutions you've written. But I understand none of them. This is my email: sororak@yahoo.com Please someone post an email to me and explain this problem to me! Thank you very much! Goodbye!

dysfunctionalequations, you seem to be considering the $a_n$'s are integer numbers... My mistake? zhu rn, I don't understand the last line of your solution. You want to write $a_n = a_{\ell} + a_{n - \ell}$... So this $k$ would be the value of $\ell$? If so... It makes some sense, but the problem asks for a value of $\ell$ which works for any $n$. Also, I think Iura's solution is correct.

Hmm, you are correct. Perhaps I should read the problem more carefully. Edit: here's a solution: We have the following claim: Claim: $a_n = \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$ for all $n > s$. Proof: by induction. The base cases $n = s+1, s+2, \cdots, 2s$ are just the given recurrence. For $n > 2s$, we clearly have $a_n = \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq n-1\}\geq \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$. Additionally, we have \[a_n = a_{j} + a_{n-j}\] for some $1\leq j \leq n-1$. WLOG, $j \geq \frac{n}{2} > s$. Therefore, by the inductive hypothesis, we have \[a_n = a_{k} + a_{j-k} + a_{n-j}\] for some $1 \leq k \leq s$. We also have $n-k > 2s - s = s$. Therefore, \begin{align*} a_n &= a_{k} + a_{j-k} + a_{n-j} \\ &\leq a_k + \max\{ a_{m}+a_{n-k - m}\mid 1\leq m\leq n-k-1\}\\ &= a_k + a_{n-k} \\ &\leq \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}. \end{align*} So $n$ is both less than or equal to and greater than or equal to $\max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$, which means it is equal to it. Now, let $l$ be a maximizer of $\frac{a_l}{l}$ for $1 \leq l \leq s$. We have the following claim: Claim: $\frac{a_n}{n} \leq \frac{a_l}{l}$ for all $n$. Proof: We induct on $n$. The base cases $n = 1, 2, \cdots, s$ result from the choice of $l$. For $n > s$, we have $a_n = a_k + a_{n-k}$ for some $k < n$, so by the inductive hypothesis \begin{align*} a_n &= a_k+a_{n-k}\\ &\leq k \frac{a_l}{l} + (n-k) \frac{a_l}{l}\\ &= n\frac{a_{l}}{l} \end{align*} implying the result. Now, define the sequence $b_n = n a_l - l a_n$. By the last claim, this is a sequence of nonnegative real numbers. Now, we have the following claim: Claim: For all $n$, $b_n$ can be expressed in the form $e_1 b_1 + e_2 b_2 + \cdots + e_s b_s$, where $e_1, e_2, \cdots, e_s$ are nonnegative integers. Proof: We, again, induct. For the base case $n \leq s$, we can choose $e_i = 1$ for $i \neq n$ and $e_n = 0$. If $n > s$, then by the first claim, we have $a_n = a_k + a_{n-k}$ for some $1 \leq k \leq s$. Therefore, $b_n = b_k + b_{n-k} =b_k+ d_1 b_1 + d_2 b_2 + \cdots + d_s b_s $ by the inductive hypothesis, where $d_1, d_2, \cdots, d_s$ are nonnegative integers. Then we can choose $e_i = d_i$ for $i \neq k$ and $e_k = d_k + 1$, and the claim is proven. Additionally, we have $b_{n+l} = (n+l) a_l - l a_{n+l} \leq (n+l) a_l - l (a_n + a_l) = b_n$. Therefore, $b_n \leq \max\{b_k\mid 1\leq k\leq l\}$ for all $n$, because every $n$ can be expressed as $r + ql$, where $1 \leq r \leq l$, and then \[b_{n} = b_{r+ql} \leq b_{r+(q-1)l} \leq \cdots \leq b_{r+l} \leq b_{r}.\] This, combined with the third claim, implies that $b_n$ only takes finitely many values, so since $b_{n+l} \leq b_n$, the sequence $b_{q}, b_{q+l}, b_{q+2l}, \cdots$ is eventually constant for all $q$, which means that $b_{n} = b_{n-l}$ for sufficiently large $n$, which rearranges to $a_{n}= a_l + a_{n-l}$, and we're done. Edit again: The third claim can actually easily be proved without the first claim, which makes the first claim unnecessary.

iura wrote: Let $t=max\{\frac {a_1}1, \frac {a_2}2, \ldots, \frac {a_s}s\}$ and let $S=\{i\mid \frac {a_i}{i}=t\}$, and choose $\ell \in S$. It is immediate by induction that $a_n\leq nt$ for all $n$. Consider now the sequence $b_n=nt-a_n$ and let's look at the $\ell$ subsequences $b_i, b_{i+\ell}, b_{i+2\ell}, \ldots$ formed by arithmetic progressions of difference $\ell$. These subsequences are (eventually) non-increasing because $a_{n+\ell}\geq a_n+a_\ell$ for $n\geq s$. On the other hand, they also take finitely many values. Indeed, each $a_n$ can be written as a sum $a_{i_1}+\ldots+a_{i_r}$ for $i_1, \ldots, i_r\in \{1, \ldots, s\}$ with $i_1+i_2+\ldots+i_r=n$ which implies $b_n=b_{i_1}+\ldots+b_{i_r}$. The quantities $b_{i_k}$ are either zero (if $i_k\in S$) or take one of the finitely many possible non-zero values in $\{b_1, \ldots, b_s\}$. In any case, since their sum is bounded (because $b_{i+m\ell}$ is eventually non-increasing in $m$), there are only finite many values for this sum (for example, we can bound the number of the occurences of each $j\not \in S$ as one of the $i_k$ by $\frac {C}{b_j}$ where $C$ is a positive constant such that $b_n\leq C$ - and we do not care for $j\in S$). Thus, each subsequence $b_i, b_{i+\ell}, b_{i+2\ell}$ is non-increasing but can only contain a finite number of distinct terms so it eventually stabilizes meaning $a_{i+(n+1)\ell}=a_{i+n\ell}+a_{\ell}$ for all sufficiently big $n$. Taking $i$ covering all residues modulo $n$ the conclusion follows. why $b_n$ take finitely many values.

dysfunctionalequations wrote: Hmm, you are correct. Perhaps I should read the problem more carefully. Edit: here's a solution: We have the following claim: Claim: $a_n = \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$ for all $n > s$. Proof: by induction. The base cases $n = s+1, s+2, \cdots, 2s$ are just the given recurrence. For $n > 2s$, we clearly have $a_n = \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq n-1\}\geq \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$. Additionally, we have \[a_n = a_{j} + a_{n-j}\] for some $1\leq j \leq n-1$. WLOG, $j \geq \frac{n}{2} > s$. Therefore, by the inductive hypothesis, we have \[a_n = a_{k} + a_{j-k} + a_{n-j}\] for some $1 \leq k \leq s$. We also have $n-k > 2s - s = s$. Therefore, \begin{align*} a_n &= a_{k} + a_{j-k} + a_{n-j} \\ &\leq a_k + \max\{ a_{m}+a_{n-k - m}\mid 1\leq m\leq n-k-1\}\\ &= a_k + a_{n-k} \\ &\leq \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}. \end{align*} So $n$ is both less than or equal to and greater than or equal to $\max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$, which means it is equal to it. Now, let $l$ be a maximizer of $\frac{a_l}{l}$ for $1 \leq l \leq s$. We have the following claim: Claim: $\frac{a_n}{n} \leq \frac{a_l}{l}$ for all $n$. Proof: We induct on $n$. The base cases $n = 1, 2, \cdots, s$ result from the choice of $l$. For $n > s$, we have $a_n = a_k + a_{n-k}$ for some $k < n$, so by the inductive hypothesis \begin{align*} a_n &= a_k+a_{n-k}\\ &\leq k \frac{a_l}{l} + (n-k) \frac{a_l}{l}\\ &= n\frac{a_{l}}{l} \end{align*} implying the result. Now, define the sequence $b_n = n a_l - l a_n$. By the last claim, this is a sequence of nonnegative real numbers. Now, we have the following claim: Claim: For all $n$, $b_n$ can be expressed in the form $e_1 b_1 + e_2 b_2 + \cdots + e_s b_s$, where $e_1, e_2, \cdots, e_s$ are nonnegative integers. Proof: We, again, induct. For the base case $n \leq s$, we can choose $e_i = 1$ for $i \neq n$ and $e_n = 0$. If $n > s$, then by the first claim, we have $a_n = a_k + a_{n-k}$ for some $1 \leq k \leq s$. Therefore, $b_n = b_k + b_{n-k} =b_k+ d_1 b_1 + d_2 b_2 + \cdots + d_s b_s $ by the inductive hypothesis, where $d_1, d_2, \cdots, d_s$ are nonnegative integers. Then we can choose $e_i = d_i$ for $i \neq k$ and $e_k = d_k + 1$, and the claim is proven. Additionally, we have $b_{n+l} = (n+l) a_l - l a_{n+l} \leq (n+l) a_l - l (a_n + a_l) = b_n$. Therefore, $b_n \leq \max\{b_k\mid 1\leq k\leq l\}$ for all $n$, because every $n$ can be expressed as $r + ql$, where $1 \leq r \leq l$, and then \[b_{n} = b_{r+ql} \leq b_{r+(q-1)l} \leq \cdots \leq b_{r+l} \leq b_{r}.\] This, combined with the third claim, implies that $b_n$ only takes finitely many values, so since $b_{n+l} \leq b_n$, the sequence $b_{q}, b_{q+l}, b_{q+2l}, \cdots$ is eventually constant for all $q$, which means that $b_{n} = b_{n-l}$ for sufficiently large $n$, which rearranges to $a_{n}= a_l + a_{n-l}$, and we're done. Edit again: The third claim can actually easily be proved without the first claim, which makes the first claim unnecessary. tank you for writing complete solution.

Just for anyone that may want to know the general "closed" formula for $a_n$: $a_n$ is the max of $b_1a_1+b_2a_2+...+b_sa_s$ for nonnegative integral $b_i$ s.t. $b_1+2b_2+...+sb_s=n$, and there exists $i,j$ s.t. $b_i \ne 0$, $b_j \ne 0$, and $i+j > s$. The proof is pretty similar to the others from here. Cheers, Rofler

My solution is similar to those posted here, but it's a little bit different, so I'll just write a sketch: here we go - We'll prove certain "facts" that will prove the problem statement. But, before this, let's make a terminology: We'll use the word $s$-division, to denote the following: For any arbitrary integer $t<s$, there exists unique integers $q_n$, $r_n$ such that $n = q_n t + r_n$ satisfying $s-t < r_n \leq s$. The $s$-quotient is $q_n$ and the $s$-remainder is $r_n$. Fix an integer $n>s$. Let a sequence $(t_1 , t_2 , ... , t_s )$ be a '$n$-good sequence' if it satisfies the following property: 1) $x_1 + 2x_2 + ... + sx_s = n$ 2) At least one of the following statements hold: a) There exists two distinct indices $i,j$ such that $x_i \ne 0$, $x_j \ne 0$, and $i+j>s$ b) There exists an index $i$ such that $x_i \geq 2$ and $2i > s$. (In other words, express $a_n$ as $a_{i_1} + a_{i_2} + ... + a_{i_k}$ where each $i_t$ satisfies $i_1 \leq i_2 \leq ... \leq i_k \leq s$, then $i_{k-1} + i_{k} > s$) Fact 1-1. When $n>s$, the sequence $a_n$ can be expressed as $ a_n = x_{1}a_{1}+x_{2}a_{2}+...+x_{s}a_{s} $ Where $(x_1 , x_2 , ... , x_s )$ is a $n$-good sequence. Proof) Use strong induction. For $n = s+1$, the problem statement is trivial ($a_{s+1} = max[a_i + a_{s+1-i}]$. The induction step is easy. Fact 1-2. For any $n$-good sequence of integers $x_i$, we have that $a_n \geq x_1 a_1 + x_2 a_2 + ... + x_s a_s$. Proof) Expand the sum as $a_{i_1} + a_{i_2} + ... + a_{i_k}$, then use the fact that $a_m + a_n \leq a_{m+n}$ if $m+n>s$. Fact 2. Denote by $b_i = \frac{a_i}{i}$, where $1 \leq i \leq s$. Assume there is a unique $i$ such that $b_i$ is maximal. For this $i$, $a_n = a_{n-i} + a_{i}$. Proof) Denote by $a = min[ b_i - b_j ] (j \neq i)$. Obviously $a > 0$. Assume the contrary, and assume there exists a sufficiently large integer $n$ such that $a_n > a_{n-i} + a_{i}$. [Claim] Express $a_{n}$ as $ a_n = x_{1}a_{1}+x_{2}a_{2}+...+x_{s}a_{s} $. Then $x_{i} \leq 2$. [Proof of Claim] Assume the contrary, and assume $x_{i} \geq 3$. Then $a_n = x_{1}a_{1}+x_{2}a_{2}+...+x_{s}a_{s} > a_{n-i} + a_{i}$ Therefore $a_{n-i} < x_{1} a_{1} + x_2 a_2 + ... + x_{i-1} a_{i-1} + (x_{i} - 1) a_i + ... + x_s a_s$ But since $(x_1 , x_2 , .. , x_{i-1} , x_{i} - 1, x_{i+1}, .. , x_s )$ is a $n-i$-good sequence, this contradicts Fact 1.2! Now, $s$-divide $n$ by $i$, and we can arrive at an easy contradiction from $ a_n = x_{1}a_{1}+x_{2}a_{2}+...+x_{s}a_{s} $ when we subtract this from $na_i$ because the coefficient of $a$ diverges, while the rest of the sum is bounded. Fact 3. Denote by $b_i = \frac{a_i}{i}$, where $1 \leq i \leq s$. Assume there are many $i$ such that $b_i$ is maximal, and let $i$ be the minimal $i$. For this $i$, $a_n = a_{n-i} + a_{i}$ for all sufficiently large $n$. Proof] Denote by $S =${$k | b_{k}$ is maximal}. Divide the sum $ a_n = x_{1}a_{1}+x_{2}a_{2}+...+x_{s}a_{s} $ by indices in $S$ and indices not in $S$. You can easily prove as in Fact 2 that the coefficients of indices in $S$ are bounded - then we again arrive at a contradiction. Fact 2,3 proves the problem statement.

The idea is to consider the sequence $a_n/n$. If you take $l \le s$ such that $L=a_l/l$ is maximal, it's easy to see that $a_l/l \ge a_m/m$ for all m. Also, since the sequence $a_i$ grows faster (or at an equal pace) than the sequence where $a_n=a_l+a_{n-l}$, then we can easily compute that the limit of $a_n/n$ is $L$, and it is always $\le L$. If we consider $b_n=n(L-(a_n/n))$, we can see that $b$ is decreasing (not necessarily strictly) if we consider only one congruence modulo $l$ of the index. But also, since $a_i$ is the sum of some $a_j$ with $j \le s$, then $b_i$ is the sum of some $b_j$ with $j \le s$. Then the sequence $b_i$ takes a finite number of values. So since it is decreasing it eventually becomes constant. At that point, we will always chose $l$. The End Really you can get the idea by considering small cases of $s$. You always get that the sequence (kind of) depends on the order of the numbers $a_1/1$, $a_2/2$, ..., $a_s/s$.

Not so bad for a #6!

JuanOrtiz wrote: Really you can get the idea by considering small cases of $s$. You always get that the sequence (kind of) depends on the order of the numbers $a_1/1$, $a_2/2$, ..., $a_s/s$. Hehe, I actually got the idea by looking at the types I mentioned above. If you use 1000, 0200, 0030, 0004 instead of 1000, 0100, 0010, 0001 then you get the nice property that at the $n$-types have sum of entries $n$. And then the rest isn't too bad from there.

I think this problem is not too hard as a p6!

Solution: Observe $a_n=a_{i_1}+a_{i_2}+\cdots a_{i_k}$ for some indices $1\le i_1, i_2, \cdots, i_k \le s$, and $i_1+i_2+\cdots i_k=n$. This is because we can write $a_n=a_{n-k}+a_k$ for some $1\le k\le n-1$ for all $n>s$, thus upon dividing this index $n$ into two parts and repeat this process as much as we can, eventually the process terminates, and we obtain the desired sequence of indices $i_1,i_2,\cdots i_k$, and sum is equal to $n$, such that $a_n=a_{i_1}+a_{i_2}+\cdots a_{i_k}$. Furthermore, if there exist another sequence of indices $j_1,j_2,\cdots j_k$, and sum is equal to $n$, then observe that for any $m,n \in \mathbb{N}$, $a_m+a_n\le a_{m+n}$, and this holds from the definition of the sequence, so inductively we can get $a_{j_1}+a_{j_2}+\cdots a_{j_k}\le a_{j_1+j_2+\cdots j_k}=a_n$. This proves that actually $$a_n=\max\{a_{i_1}+a_{i_2}+\cdots a_{i_k}\mid 1\le i_1, i_2, \cdots, i_k \le s,\enspace i_1+i_2+\cdots i_k=n\}$$ Now define $1\le \ell \le s$ be the $\ell$ such that $\frac{a_\ell}{\ell}$ is maximal. We claim that this works. Consider the sum for $a_n$ into smaller terms. First, if $a_j$ appears $\ell$ times in the sum $a_{i_1}+a_{i_2}+\cdots +\ell a_j+\cdots $, then replace it with $a_\ell$ appearing $j$ times, which is $a_{i_1}+a_{i_2}+\cdots +j a_\ell+\cdots $. By maximality of $\ell$, we have $$a_n=a_{i_1}+a_{i_2}+\cdots +\ell a_j+\cdots \le a_{i_1}+a_{i_2}+\cdots +j a_\ell+\cdots $$And by the definition of $a_n$, we conclude that both sums must be equal, so $a_n=a_{i_1}+a_{i_2}+\cdots +j a_\ell+\cdots $. Now let us take $N=s(1+2+\cdots +s)$. Clearly $N>\ell(1+2+\cdots +s)$, and we claim that there is a sum for $a_n$ that contains $a_\ell$ in it. This is because if the sum for $a_n$ has no $a_\ell$ in it, then by Pigeonhole principle, there is an index that appears more than $\ell$ times, say $a_j$, then we may repeat the above modification as described, and eventually the new sum in $a_n$ has $a_\ell$ in it. So the claim is proven. With this, write $$a_n=a_{i_1}+a_{i_2}+\cdots +a_{i_{m-1}}+a_\ell$$Then by the inequality $a_m+a_n\le a_{m+n}$ again, then $$a_n=a_{i_1}+a_{i_2}+\cdots +a_{i_{m-1}}+a_\ell\le a_{i_1+i_2+i_{m-1}}+a_\ell=a_{n-\ell}+a_\ell$$Thus $a_n\le a_{n-\ell}+a_\ell$, which by the inequality means $a_n=a_{n-\ell}+a_\ell$ for all $n>s(1+2+\cdots +s)=\frac{s^2(s+1)}{2}$, and we are done!

Note that we can show inductively that for each $n$, there are nonnegative integers $c_1,...,c_s$ such that $a_n=\sum_{k=1}^s c_k\cdot a_k$ with $\sum_{k=1}^s c_k\cdot k=n$ - just use the fact that $a_n=a_t+a_{n-t}$ for some $1\le t\le n-1$. Moreover, we can also show inductively that if $c_1', ..., c_s'$ are integers such that $\sum_{k=1}^s c_k\cdot k=n$, then $a_n\ge \sum_{k=1}^s c_k'\cdot a_k$. Indeed, if $a_n<\sum_{k=1}^s c_k'\cdot a_k$, then note that if we take $c_m>0$ and $c_k''=c_k'$ when $k\neq m$, $c_m'-1$ otherwise, then $$a_n<\sum_{k=1}^s c_k'\cdot a_k=a_m+\sum_{k=1}^s c_k''\cdot a_k\le a_m+a_{n-m}$$by the inductive hypothesis, contradiction! Using this, we have that if $c_\ell > 0$, then that $$a_n=\sum_{k=1}^s c_k\cdot a_k = a_\ell + \sum_{k=1}^s c_k'\cdot a_k \le a_\ell + a_{n-\ell}$$where $c_k'=c_k$ when $k\neq \ell$ and $c_\ell -1$ otherwise. But note that $a_n\ge a_\ell + a_{n-\ell}$ by definition, so we have $a_n=a_\ell + a_{n-\ell}$. Now we claim that for $n$ large, there is some fixed $\ell$ with $c_\ell >0$ for $n$ large. Let $\ell$ be such that $\frac{a_\ell}{\ell}=\max_{k=1,...,s} \left(\frac{a_k}{k}\right)$. Take $a_n=\sum_{k=1}^s c_k\cdot a_k$. Take $n$ large, and suppose for the sake of contradiction $c_\ell=0$. For $n$ large, we must have $c_m>\ell$ for some $m$. But note that $$c_m\cdot a_m=(c_m-\ell)\cdot a_m + \ell \cdot a_m \le (c_m-\ell) \cdot a_m + m\cdot a_\ell$$In particular, replacing $c_m$ with $c_m-\ell$ and $c_\ell=0$ with $c_\ell = m$ can only optimize $a_n$. Thus $c_\ell>0$ for $n$ large, and thus $a_n=a_\ell + a_{n-\ell}$ as desired. $\square$

Aaaaaaaa

iura wrote: Let $t=max\{\frac {a_1}1, \frac {a_2}2, \ldots, \frac {a_s}s\}$ and let $S=\{i\mid \frac {a_i}{i}=t\}$, and choose $\ell \in S$. Thus, each subsequence $b_i, b_{i+\ell}, b_{i+2\ell}$ is non-increasing but can only contain a finite number of distinct terms so it eventually stabilizes meaning $a_{i+(n+1)\ell}=a_{i+n\ell}+a_{\ell}$ for all sufficiently big $n$. Taking $i$ covering all residues modulo $n$ the conclusion follows. Sorry for reviving this topic, but shouldn't it be all the residues modulo $\ell$? Thanks!

Let $b_n=\dfrac{a_n}{n}$. Let $b_p=\max \{b_n|n\leq s \}$. By induction, $b_n \leq b_p$. Define $c_n=b_pn-a_n$. Note that $c_p=0$, $c_n= \min \{ c_k+c_{n-k} \}$ for all $n>s$ and all $c_n$ are nonnegative. We have $c_n \leq c_p + c_{n-p}=c_{n-p} \leq \max \{c_1, \ldots, c_{n-1} \}$ for all $n > s$, so $c_n$ is bounded. Also, by induction every $c_n$ is a linear combination of $c_1, \ldots c_s$ with nonnegative coefficients, so $c_n$ take only finitely many values. For any $r<p$ and $k$ with $kp+r>s$ we have that $c_{(k+1)p+r} \leq c_p + c_{kp+r} = c_{kp+r}$, so the sequence $c_{kp+r}$ is nonincreasing from some point and takes finitely many values, and hence eventually constant. Then there exists $N$ such that for all $n\geq N$ $c_n=c_{n-p} \implies a_n=a_{n-p}+a_p$, QED.

Much to my horror I find that the solution I posted here four years ago is not correct. Here is what I hope is a correct one. Let \[ w_1 = \frac{a_1}{1}, \quad w_2 = \frac{a_2}{2}, \quad \dots, \quad w_s = \frac{a_s}{s}. \](The choice of the letter $w$ is for ``weight''.) We claim the right choice of $\ell$ is the one maximizing $w_\ell$. Our plan is to view each $a_n$ as a linear combination of the weights $w_1, \dots, w_s$ and track their coefficients. To this end, let's define an $n$-type to be a vector $T = \left< t_1, \dots, t_s\right>$ of nonnegative integers such that $n = t_1 + \dots + t_s$; and $t_i$ is divisible by $i$ for every $i$. We then define its valuation as $v(T) = \sum_{i=1}^s w_i t_i$. Now we define a $n$-type to be valid according to the following recursive rule. For $1 \le n \le s$ the only valid $n$-types are \begin{align*} T_1 &= \left< 1, 0, 0, \dots, 0 \right> \\ T_2 &= \left< 0, 2, 0, \dots, 0 \right> \\ T_3 &= \left< 0, 0, 3, \dots, 0 \right> \\ &\vdots \\ T_s &= \left< 0, 0, 0, \dots, s \right> \end{align*}for $n = 1, \dots, s$, respectively. Then for any $n > s$, an $n$-type is valid if it can be written as the sum of a valid $k$-type and a valid $(n-k)$-type, componentwise. These represent the linear combinations possible in the recursion; in other words the recursion in the problem is phrased as \[ a_n = \max_{T \text{ is a valid $n$-type}} v(T). \] In fact, we have the following description of valid $n$-types: Claim: Assume $n > s$. Then an $n$-type $\left< t_1, \dots, t_s \right>$ is valid if and only if either there exist indices $i < j$ with $i+j > s$, $t_i \ge i$ and $t_j \ge j$; or there exists an index $i > s/2$ with $t_i \ge 2i$. Proof. Immediate by forwards induction on $n > s$ that all $n$-types have this property. The reverse direction is by downwards induction on $n$. Indeed if $\sum_i \frac{t_i}{i} > 2$, then we may subtract off on of $\{T_1, \dots, T_s\}$ while preserving the condition; and the case $\sum_i \frac{t_i}{i} = 2$ is essentially by definition. $\blacksquare$ Remark: The claim is a bit confusingly stated in its two cases; really the latter case should be thought of as the situation $i=j$ but requiring that $t_i/i$ is counted with multiplicity. Now, for each $n > s$ we pick a valid $n$-type $T_n$ with $a_n = v(T_n)$; if there are ties, we pick one for which the $\ell$th entry is as large as possible. Claim: For any $n > s$ and index $i \ne \ell$, the $i$th entry of $T_n$ is at most $2s + \ell i$. Proof. If not, we can go back $i\ell$ steps to get a valid $(n-i\ell)$-type $T$ achieved by decreasing the $i$th entry of $T_n$ by $i \ell$. But then we can add $\ell$ to the $\ell$th entry $i$ times to get another $n$-type $T'$ which obviously has valuation at least as large, but with larger $\ell$th entry. $\blacksquare$ Now since all other entries in $T_n$ are bounded, eventually the sequence $(T_n)_{n > s}$ just consists of repeatedly adding $1$ to the $\ell$th entry, as required. Remark: One big step is to consider $w_k = a_k / k$. You can get this using wishful thinking or by examining small cases. (In addition this normalization makes it easier to see why the largest $w$ plays an important role, since then in the definition of type, the $n$-types all have a sum of $n$. Unfortunately, it makes the characterization of valid $n$-types somewhat clumsier too.)

mavropnevma wrote: Let $a_1, a_2, a_3, \ldots$ be a sequence of positive real numbers, and $s$ be a positive integer, such that \[a_n = \max \{ a_k + a_{n-k} \mid 1 \leq k \leq n-1 \} \ \textrm{ for all } \ n > s.\]Prove there exist positive integers $\ell \leq s$ and $N$, such that \[a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N.\] Proposed by Morteza Saghafiyan, Iran By the way, Does anyone knows who is this aops user Mavropnevma? I found most of his/her solutions are extremely beautiful.

He is Dan Schwartz from Romania. Unfortunately, he died four years ago.

The above defined sequence is a superadditive sequence [1]. According to Michael Fekete's lemma, the limit $\lim\limits_{n\to\infty} \frac{a_n}{n}$ exists and equals to $\text{sup}\frac{a_n}{n}$. If the claim of the problem is correct, then one must have $\lim\limits_{n\to\infty} \frac{a_n}{n} = \frac{a_l}{l}$. Therefore, $\frac{a_l}{l} = \text{sup}\frac{a_n}{n}$. Now, it follows why the index $l$ must be $\underset{1\le k\le s}{\text{arg max}} \frac{a_k}{k}$. 1. https://en.wikipedia.org/wiki/Superadditivity

Let $k$ be in $[1,s]$ such that $$\frac{a_k}{k} = \max_{i=1}^s\left\{\frac{a_i}{i}\right\}$$We will prove that this $k$ satisfies $a_n=a_k+a_{n-k}$ for sufficiently large $n$. First, by induction, $\frac{a_n}{n} \le \frac{a_k}{k}$ for all positive integers $n$. So let $u=\frac{a_k}{k}$, and $$b_n = nu - a_n \ge 0$$for each $n$. Then it suffices to prove $b_n = b_{n-k}$ for sufficiently large $n$. Fix a residue $j$, $1\le j \le k$, and take a subsequence $(b_{j+km})$ for $m\in\mathbb{Z}_+$. This subsequence is eventually non-increasing because $a_{j+km} \ge a_{j+k(m-1)}+a_k$ for $m$ large enough. Furthermore, this subsequence only takes on finitely many values because it's bounded and every term is a linear combination (with integer coefficients) of $b_1,b_2,\dots, b_s$. Therefore the sequence is eventually constant. Now let $j$ range from $1$ to $k$, then for each residue the subsequence is eventually constant. Therefore $b_n = b_{n-k}$ for sufficiently large $n$.

easy for P6. Note that $a_n\ge a_k+a_{n-k} $ $\forall k< n$, hence $a_n\ge a_{x_1}+....a_{x_k} , x_1+x_2+...x_k=n.... (1)$. By easy induction we get that each $a_n$ can be written as $ a_{x_1}+a_{x_2}+.....a_{x_k} $ where $x_i <s $ and $x_1+...+x_k=n$. Let let $l<s$ be such that, $\frac{a_l}{l} $ is maximized, we prove that this is the desired index. if $a_{x_i}=a_l $ for some $i$ then we are done by applying $(1)$. If not, then for big enough $n $, there will be $l $ equal numbers from $ a_{x_i} 's $, let them equal to $m<s$, hence we can replace them with $m$ of $a_l 's$ and we get a bigger value for $a_n$ a contradiction.

Claim: Every $a_n$ with $n>s$ can be written as $a_k+a_{n-k}$ where $k\le s$ Proof: Suppose otherwise, and consider the first $a_n$ which cannot be written in this form. Then, $a_n=a_k+a_{n-k}$ with $k>s$, and by minimality we can write $a_k=a_i+a_{k-i}$ with $k\le s$. This means that $a_n=a_i+(a_{n-k}+a_{k-i})$. However, we have $a_n=a_i+(a_{n-k}+a_{k-i})\le a_i+a_{n-i}\le a_n$, so equality holds everywhere and $a_n=a_i+a_{n-i}$, which is a contradiction, as desired. Now, let $j$ be the number in $[s]$ where $\frac{a_j}{j}$ is maximized. We claim that $a_n=a_j+a_{n-j}$ for all sufficiently large $n$. First, consider the directed graph where we have $i\to i+k$ if $a_{i+k}=a_i+a_k$ with $k\le s$. As all vertices must have indegree $1$ by our claim, we can backtrack from a given $n$ to form a chain. In particular, choose $n>s(j+1)$, which forces the chain to have length at least $j$. Suppose our chain is comprised of $a_{b_0}\to a_{b_1}\to a_{b_2}\to \ldots\to a_{b_k}$ where $b_k=n$. Then, as $k\ge j$, two of the $b_i$ must have the same residue mod $j$. Suppose that $b_y-b_x=j\cdot C$. Now, we know that $$a_{b_y}-a_{b_x}=(a_{b_{y}-b_{y-1}}+a_{b_{y-1}-b_{y-2}}+\ldots +a_{b_{x+1}-b_x})\le \frac{a_j}{j}(b_y-b_{y-1}+\ldots+b_{x+1}-b_x)=a_jC$$while we also have that $$a_{b_y}\ge a_{b_y-j}+a_j\ge \ldots \ge a_{b_x}+a_jC$$So, $a_{b_y}-a_{b_x}=a_jC$, and thus we can replace the section of the chain with only edges of length $j$. In particular, this means that there exists a chain which contains $a_n$ which also has an edge of length $j$. However, note that we can permute the lengths of the edges without changing the endpoints, implying that any permutations of the lengths still produces a valid chain, by similar inequalities to above. Then, just permute the edge of length $j$ to the last edge to get that $a_{n-j}\to a_n$ is a valid edge. Thus, $a_n=a_j+a_{n-j}\forall n>s(j+1)$, and we are done.

Choose $d \le s$ such that $\frac{a_d}{d} \geq \frac{a_k}{k}$ for all $1 \leq k \leq s$. Then, $a_{s+1} \leq \frac{ka_d}{d}+\frac{(s+1-k)a_d}{d} \implies \frac{a_{s+1}}{s+1} \leq \frac{a_d}{d} \implies$ by induction, $\frac{a_d}{d} \geq \frac{a_n}{n}$ for all $n$. Furthermore, $a_n \geq a_d+a_{n-d} \geq \frac{da_{n-d}}{n-d}$. Hence, since $\frac{a_n}{n}$ is bounded, the $a_n$’s can be written as a linear combination of $a_i$, with $ i \leq s$, and $\frac{a_n}{n}$ is eventually non-decreasing, $\frac{a_n}{n}$ is eventually constant according with its residue $\pmod d$. $$\implies \frac{a_n}{n}=\frac{a_{n+d}}{n+d}$$for $n$ sufficiently large. $\implies a_{n+d} \geq a_n+a_d \geq a_n+ \frac{da_n}{n}=a_{n+d} \implies a_{n+d}=a_n+a_d$ for $n$ large enough, as desired. $\blacksquare$

Not too hard for a P6 Storage: For a positive integer $n>s$, call a representation of it a finite sequence $s \geq d_1 \geq d_2 \geq \cdots d_m >0$ such that $d_1+d_2+\cdots d_m=n$ and $d_1+d_2>s$. The value of a representation is just the sum $a_{d_1}+a_{d_2}+ \cdots a_{d_m}$. Lemma 1: For any $n>s$, the maximum value of any representation of $n$ is $a_n$. Proof: We can obtain $a_n$ as the value of some representation of $n$ easily by using the given condition and induction. Conversely, given any representation $d_1,d_2, \dots d_m$ of $n$, we must have $$a_{d_1}+a_{d_2}+ \cdots a_{d_m} \leq a_{d_1+d_2} + \cdots a_{d_m} \leq \cdots \leq a_{d_1+d_2+\cdots d_m}=a_n$$as required. $\blacksquare$ Call a representation perfect if its value is $a_n$. Lemma 2: For any perfect representation $d_1,d_2, \dots d_m$ of $n$, and any $2<i \leq m$, we have $a_n=a_{d_i}+a_{n-d_i}$. Proof: Note that $d_1,d_2, \dots d_{i-1}, d_{i+1}, \dots d_m$ is a representation of $n-d_i$ because $d_1$ or $d_2$ are not removed. Therefore $$a_{d_i}+a_{n-d_i} \geq a_{d_1}+a_{d_2}+ \cdots a_{d_m} = a_n \geq a_{d_i}+a_{n-d_i}$$$\implies$ $a_n=a_{d_i}+a_{n-d_i}$ as required. $\blacksquare$ Choose an $l \leq s$ satisfying $\dfrac{a_l}{l} \geq \dfrac{a_k}{k}$ for all $k \leq s$ (writing $\ell$ every time is a pain in the neck). For any $n>s$ and any perfect representation $\mathcal{R}$ of $n$, if some $k \neq l$ appears at least $l+2$ times, we can replace $l$ occurrences of $k$ with $k$ occurrences of $l$ to get a new representation $\mathcal{R}'$. Note that $\mathcal{R}'$ is indeed a representation because the sum is still $n$, and $k$ still appears at least twice in it, so sum of the two largest numbers would still be $>s$. Also note that, since $la_k \leq ka_l$, the value of $\mathcal{R}'$ is at least the value of $\mathcal{R}$; but the latter is $a_n$, and the former is at most $a_n$ $\implies$ The value of $\mathcal{R}'$ is $a_n$ $\implies$ $\mathcal{R}'$ is perfect as well. Doing this repeatedly, we will obtain a perfect representation of $n$ where every $k \neq l$ occurs at most $l+1$ times. Call such a representation cute. Finally, note that if $n>(l+4)(1+2+\cdots s)$, then $l$ must appear at least $3$ times in any cute representation of $n$. Thus, if the cute representation is $d_1,d_2, \dots d_m$, then $l=d_i$ for some $i \geq 3$. Therefore, by Lemma 2, $$a_n=a_l + a_{n-l}$$for all sufficiently large positive integers $n$. $\blacksquare$

Consider the positive integer $k$ where $k \le s$ such that $\frac{a_k}{k} = \max\left\{\frac{a_i}{i} \mid 1 \le i \le s\right\}$. I will show for large $N$ that $$a_n = a_k + a_{n - k} \ \textrm{ for all } \ n > N.$$ First by our assumption on $k$, we have a lemma: Lemma: For all $i > s$, we have $\frac{i \cdot a_k}{k}\ge a_i \ge a_{i-k}+a_k$. Now, for some integers $0 \le p < k$, let $A_p$ be a sequence of all $a_i$ where $i \equiv p \pmod k$. Additionally, let $B_p$ be the sequence of values $\frac{a_i}{i}$ where $i \equiv p \pmod k$. Note by our lemma that $B_p$ is a nondecreasing sequence capped at the value of $\frac{a_k}{k}$. We let two numbers $\frac{a_i}{i}$ and $\frac{a_j}{j}$ to be "distinct" if $a_i-a_j \ne \frac{(i-j)a_k}{k}$. Therefore, there are also a finite number of distinct numbers in this sequence, and let this be $c_p$. Similarly, define $c_0, c_1, \ldots c_{k-1}$. Notice that the finite number $\sum_{i = 0}^{k-1} c_i$ is the exact number of values of $a_x$ where $a_x \ne a_k+a_{x-k}$. I will now a prove a claim: Claim: Let $p$ be an integer in the range $[s+ck, s+dk)$ where $s+dk > 69(s+ck)$. If all $a_p = a_{p-k}+a_k$, then $a_q = a_{q-k}+a_k$ for all $q \ge s+dk$. Proof: Assume otherwise, then let $q$ be the smallest number greater than or equal to $s+dk$ such that $a_q = a_{q-l}+a_l > a_k+a_{q-k}$ for some positive integer $l \le \frac{q}{2}$. Notice that $$a_{q-k} = a_k+a_{q-2k} \ge a_l+a_{q-k-l} \implies a_{q-l}+a_l-k > a_l+a_{q-2l} \implies a_{q-l}-k > a_{q-k-l}$$which is false as they are equal to each other by our hypothesis. $\square$ Therefore, because there are a finite number of $a_i$ where $a_i \ne a_k+a_{i-k}$, and their indices have a finite difference between one another by our claim, that means there exists an arbitrarily large $N$ where $$a_n = a_{k} + a_{n - k} \ \textrm{ for all } \ n \geq N$$as desried. $\blacksquare$ Remarks: This problem is quite nice but I found it quite hard. Thinking about $\frac{a_k}{k}$ was actually the easy part for me as it is motivated by just trying random sequences. The hard part for me was showing that the $a_i$ where $a_i \ne a_k+a_{i-k})$ are bounded above, which finishes by the claim that there is a finite amount of these $a_i$.

Choose $t \in \{1,2,\ldots,s\}$ that maximizes $\frac{a_t}{t}$, and let $b_n=a_n-n\frac{a_t}{t}$. Notice that $b_n$ satisfies the same recurrence relation as $a_n$. We see that $b_1,b_2,\ldots,b_s$ are nonpositive and at least one of these is $0$, so all terms of $\{b_n\}$ are negative. We claim that $\{b_n\}$ is eventually periodic. Observe that if $b_n=0$, then $b_{kn}=0$ for any positive integer $k$. Calculate terms of $b_n$ until we find a number $d>s$ such that $b_d=0$. Define \[S=\{w_1b_1+w_2b_2+\cdots+w_sb_s \mid w_1,w_2,\ldots,w_s \in \mathbb{Z}\}.\]Notice that the number of elements of $S$ greater than any real number is finite. By induction, we can show that all terms of $\{b_n\}$ are in $S$. Since $b_{n+d} \leq b_n+b_d=b_n$, we know that each of the sequences \[a_1,a_{1+d},a_{1+2d},\ldots\]\[a_2,a_{2+d},a_{2+2d},\ldots\]\[\vdots\]\[a_{d-1},a_{d-1+d},a_{d-1+2d},\ldots\]are eventually constant. Thus, $\{b_n\}$ is eventually periodic.

Define the function $b_n=\frac{a_n}{n}$. By induction, we claim that if $b = \max_{1\le k\le s} b_s$, then $b_n \le b$. Let $b_k=b$. For $n\le s$, the result is clear. Otherwise, there exists $1\le k\le n-1$ with $nb_n = kb_k + (n-k)b_{n-k} \le kb + (n-k)b = nb$, so we are done with the claim. Now, for each integer $1\le e\le k$, we prove that there exists $N_e$ such that $n>N_e$ implies $a_{s+n_ek+e} = a_k + a_{s+(n_e-1)k+e}$; this suffices. Consider the sequence \[\{(s+nk+e)a_k - ka_{s+nk+e}\}_{n\ge 0}^\infty.\]Each term is nonnegative because $b_{s+nk+e} \le b_k$. Each term is an integer. Moreover, the sequence is nonincreasing because \[(s+(n+1)k+e)a_k - ka_{s+(n+1)k+e} \le (s+nk+e)a_k + ka_k - k[a_{s+nk+e}+a_k] = (s+nk+e)a_k - ka_{s+nk+e}.\]Thus it is fixed for $n\ge N_e$ for some integer $N_e$. In turn, this implies that for $n>N_e$, we have \[(s+(n+1)k+e)a_k - ka_{s+(n+1)k+e} = (s+nk+e)a_k+ka_k - k[a_{s+nk+e}+a_k],\]which is equivalent to the desired result.

The problem becomes much easier if you recognize that the sequence here is very similar to the function defined by the dynamic programming algorithm for the knapsack problem, where there are items of cost $1, 2, \dots, s$ with values $a_1, a_2, \dots, a_s$ respectively, and have the intuition that you should, in the long term, prefer the item with the best "benefit-cost ratio". (@Rofler's post #14 makes the notion of equivalence to the knapsack problem precise, and explains the slight caveat in that the way the sequence is defined here forces choosing two items whose costs sum to more than $s$. I think there is a minor error in their post, in that in the case of $i=j$, it is also necessary that $b_i \ge 2$, but that doesn't affect the proof much.)

We have the following claim: Claim: $a_n = \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$ for all $n > s$. Proof: by induction. The base cases $n = s+1, s+2, \cdots, 2s$ are just the given recurrence. For $n > 2s$, we clearly have $a_n = \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq n-1\}\geq \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$. Additionally, we have\[a_n = a_{j} + a_{n-j}\]for some $1\leq j \leq n-1$. WLOG, $j \geq \frac{n}{2} > s$. Therefore, by the inductive hypothesis, we have\[a_n = a_{k} + a_{j-k} + a_{n-j}\]for some $1 \leq k \leq s$. We also have $n-k > 2s - s = s$. Therefore, \begin{align*} a_n &= a_{k} + a_{j-k} + a_{n-j} \\ &\leq a_k + \max\{ a_{m}+a_{n-k - m}\mid 1\leq m\leq n-k-1\}\\ &= a_k + a_{n-k} \\ &\leq \max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}. \end{align*}So $n$ is both less than or equal to and greater than or equal to $\max\{ a_{k}+a_{n-k}\mid 1\leq k\leq s\}$, which means it is equal to it. Now, let $l$ be a maximizer of $\frac{a_l}{l}$ for $1 \leq l \leq s$. We have the following claim: Claim: $\frac{a_n}{n} \leq \frac{a_l}{l}$ for all $n$. Proof: We induct on $n$. The base cases $n = 1, 2, \cdots, s$ result from the choice of $l$. For $n > s$, we have $a_n = a_k + a_{n-k}$ for some $k < n$, so by the inductive hypothesis \begin{align*} a_n &= a_k+a_{n-k}\\ &\leq k \frac{a_l}{l} + (n-k) \frac{a_l}{l}\\ &= n\frac{a_{l}}{l} \end{align*}implying the result. Now, define the sequence $b_n = n a_l - l a_n$. By the last claim, this is a sequence of nonnegative real numbers. Now, we have the following claim: Claim: For all $n$, $b_n$ can be expressed in the form $e_1 b_1 + e_2 b_2 + \cdots + e_s b_s$, where $e_1, e_2, \cdots, e_s$ are nonnegative integers. Proof: We, again, induct. For the base case $n \leq s$, we can choose $e_i = 1$ for $i \neq n$ and $e_n = 0$. If $n > s$, then by the first claim, we have $a_n = a_k + a_{n-k}$ for some $1 \leq k \leq s$. Therefore, $b_n = b_k + b_{n-k} =b_k+ d_1 b_1 + d_2 b_2 + \cdots + d_s b_s $ by the inductive hypothesis, where $d_1, d_2, \cdots, d_s$ are nonnegative integers. Then we can choose $e_i = d_i$ for $i \neq k$ and $e_k = d_k + 1$, and the claim is proven. Additionally, we have $b_{n+l} = (n+l) a_l - l a_{n+l} \leq (n+l) a_l - l (a_n + a_l) = b_n$. Therefore, $b_n \leq \max\{b_k\mid 1\leq k\leq l\}$ for all $n$, because every $n$ can be expressed as $r + ql$, where $1 \leq r \leq l$, and then\[b_{n} = b_{r+ql} \leq b_{r+(q-1)l} \leq \cdots \leq b_{r+l} \leq b_{r}.\]This, combined with the third claim, implies that $b_n$ only takes finitely many values, so since $b_{n+l} \leq b_n$, the sequence $b_{q}, b_{q+l}, b_{q+2l}, \cdots$ is eventually constant for all $q$, which means that $b_{n} = b_{n-l}$ for sufficiently large $n$, which rearranges to $a_{n}= a_l + a_{n-l}$, and we're done. Edit again: The third claim can actually easily be proved without the first claim, which makes the first claim unnecessary.

Let $r=\max\{a_i/i\}$; by induction it follows that $a_n \leq rn$ for all $n$. Now note that shifting the term $a_i$ by $ti$ for some $t \in \mathbb{R}$ doesn't change anything, so WLOG shift so that $r=0$ and $a_n \leq 0$ for all $n$. Let $S=\{i \mid a_i/i=r\}$ and let $d=\gcd(S)$. Using Bezout's theorem it easily follows that every sufficiently large positive multiple of $d$ can be written as a positive integer linear combination of elements in $S$. Furthermore, if $a_n=0$ then we require $d \mid n$. For $1 \leq i<d$, let $s_i$ denote the sequence $a_i,a_{i+d},a_{i+2d},\ldots$. It is clear that $s_i$ is nondecreasing, and since its terms are always negative it's bounded above, hence has a limit/supremum $L_i$. Furthermore, since all nonzero terms of the sequence are bounded above by the largest nonzero element of $a_1,\ldots,a_s$, no $L_i$ can equal $0$. I now claim that $s_i$ eventually always equals this unit. To prove this, we induct from the largest $L_i$ to the smallest. Fix some $i$ and suppose that $s_j$ is eventually constant for all $j$ such that $L_j>L_i$. If there exist $j_1,j_2$ such that $j_1+j_2 \equiv i \pmod{d}$ (with $j_1,j_2 \neq i$), and $L_{j_1}+L_{j_2}>L_i$, we contradict the definition of $L_i$ since we can find terms in $s_i$ which are equal to $L_{j_1}+L_{j_2}$. If such indices exist such that $L_{j_1}+L_{j_2}=L_i$, then we can again find terms in $s_i$ which are equal to $L_{j_1}+L_{j_2}$ by the inductive hypothesis (note that no $L_j$ are $0$), so $s_i$ achieves its supremum and thus must be eventually equal to it. Otherwise, suppose we have $k$ such that $a_{i+kd}$ is greater than $L_{j_1}+L_{j_2}$ for all $j_1+j_2 \equiv i \pmod{d}$, and $a_{i+kd}$ is greater than $1.5L_i$—this is true for all large enough $k$. Then $a_{i+(k+1)d}=a_{i+kd}$, since it's at least this quantity from $a_{i+(k+1)d} \geq a_{i+kd}+a_d$, but on the other hand if $a_{i+(k+1)d}=a_{j_1}+a_{j_2}$ where $d \nmid j_1,j_2$ then $a_{j_1}+a_{j_2} \leq L_{j_1}+L_{j_2}<a_{i+kd}$. Hence $s_i$ is also eventually constant. This implies that $a_n=a_{n-d}$ for all sufficiently large $d$, so picking any $\ell \in S \implies d \mid \ell$, we have $a_n=a_{n-\ell}$ for all sufficiently large $n$. $\blacksquare$ Remark: Missed the fact that elements of the sequence are "discrete" in the sense that you can write them as positive linear combinations of $a_1,\ldots,a_n$, which makes this solution a bit more complicated. Idea is the same though.

my brain lacks power (this is probably a fakesolve lmao idk) Take $\ell\le s$ where $\frac{a_\ell}{\ell}$ is maximal. First we prove by strong induction that $\frac{a_n}{n}\le \frac{a_\ell}{\ell}$ always holds. Suppose $a_n=a_k+a_{n-k}$ where $n>s$ then write (I procrastinated this step for a long time, not sure why oops. Intuition bad!!!) \[\frac{k}{n}\cdot \frac{a_k}{k}+\frac{n-k}{n}\cdot \frac{a_{n-k}}{n-k}=\frac{a_n}{n}\]and notice that base case $n=s+1$ is trivial by assumption. The LHS is essentially a weighted average of $\frac{a_k}{k},\frac{a_{n-k}}{n-k}\le \frac{a_\ell}{\ell}$, hence proven. The idea now is to prove that $f(n)=a_n-\frac{a_\ell}{\ell}\cdot n$ is bounded above and below. The motivation for this is actually very interesting. By the truth of the problem statement, we find that $a_n$ grows linearly. We can also find that $a_\ell \le a_{n+\ell}-a_n$ which implies that $a_n-\frac{a_\ell}{\ell}\cdot n$ is bounded below (for any $\ell$). Again by the truth of the problem statement, this eliminates all values of $\ell$ except for the one where $\frac{a_\ell}{\ell}$ is maximal. It also implies the claim $\frac{a_n}{n}\le \frac{a_{\ell}}{\ell}$ in general, very interesting! Well actually from my rambling above we already have that the quantity is bounded below: since \[a_\ell\le a_{n+\ell}-a_n\implies a_{n+\ell}\ge a_n+a_\ell\]it follows that the function value is nondecreasing when adding integer multiples of $\ell$ to some indices $a_{m+1},\dots,a_{m+\ell}$. So the function's minimal value would be at least the minimal value at one of the values $a_{m+1},\dots,a_{m+\ell}$. To prove it's bounded above, just note the function is nonpositive by our claim. Now take some index $a_m$ and suppose that \[a_{m+(k+1)\ell}-a_{m+k\ell}>a_\ell\]for infinitely many $k$. This is a very simple contradiction to our claim that $f$ is bounded above and below, since \[f(a_{m+(k+1)\ell})\ge f(a_{m+k\ell})+1\]yay!

better written version: Step 1. Take $\frac{a_\ell}{\ell}$ maximal where $\ell\le s$. By strong induction, prove $\frac{a_n}{n}\le \frac{a_\ell}{\ell}$ always. Step 2: Define the function $f(n)=a_n-\frac{a_\ell}{\ell}\cdot n$. From \[a_{n+\ell}\ge a_n+a_\ell\]prove that $f$ is bounded below. From Step 1 prove that $f$ is bounded above. Step 3: Conclude by FTSOC by showing that \[a_{m+(k+1)\ell}-a_{m+k\ell}>a_\ell\]cannot occur for infinitely many/arbitrarily large $k$. Actually we don't need $f$ bounded below; technically we just have to note $a_{n+\ell}\ge a_n+a_\ell$ after Step 3 and we're done. ok this should be post #5 not a fakesolve yay.,

If $a_n=a_k+a_{n-k}$ for $n>s$, where $k$ is minimal, say $n$ chooses k. Lemma 1 Every number chooses a number $\leq s$ Proof: By induction on $n$. $n=s+1$ is obvious. For the sake of contradiction, suppose $a_n=a_m+a_{n-m}$, where $n-m \geq m>s$. Let $a_m=a_k+a_{m-k}$, by induction $k \leq s$. Then $a_n=a_m+a_{n-m}=a_k+a_{m-k}+a_{n-m} \leq a_k+a_{n-k}<a_n$ - contradiction. Done Observation: $a_{n+1} \geq a_n+a_1 > a_n$, so $\{a\}$ is increasing. Now let every number draw an arrow to it-chosen (i.e. $n$ draws an arrow to $n-k$, where $a_n=a_k+a_{n-k}$ and $n$ chose k). Now redirect all the arrows to the opposite. Now all chains start from $1,\ldots,s$ The main idea is that we will prove that this $l$ in the problem statement is actually such a number that $\frac{a_l}{l}$ is maximal, where $l \leq s$. Let $l_1,\ldots,l_m$ be all numbers with this maximal value $v$, call them elite. And let $t$ be the second biggest value attained (if no such in the end of the solution) Consider any biiig number $n$. Trace it by arrows to the furthest moment when the remainder of distance to $n$ when divisible by $l_1$ is $\leq s$ (Obviously, it exists, also this moment will obviously be at some point $\leq const$, cause otherwise we can continue). Okey, let us have in our path non-elite steps by $a_{i_1},\ldots, a_{i_k}$ and a total distance $s'$ of elite steps. $bl_1+r$ is the total distance of our path. Then $bl_1+r=i_1+\ldots+i_k+s'$, from which $i_1+\ldots+i_k=bl_1+r-s'$. But $a_n=a_{n-(bl_1+r)}+a_{i_1}+\ldots+a_{i_k}+vs'=a_n > a_{n-bl_1}+ba_{l_1}> a_{n-bl_1-r}+ba_{l_1}$, from which $t(bl_1+r-s')+vs'=t(i_1+\ldots+i_k)+vs' \geq a_{i_1}+\ldots+a_{i_k}+vs'>ba_{l_1}=bvl_1$, which rewrites as $$ts \geq tr>(v-t)(bl_1-s')$$Note that it says that $bl_1-s'$ is bounded, so $bl'+r-s' \leq bl_1-s'+s$ is bounded, but the latter is the total distance covered by non-elite jumps. Because every jump is at least one, the number of non-elite jumps is bounded. Now note that this actually means the number of non-elite jumps in the whole system is bounded(one can easily formally prove it by induction, for example). Thus, from some point all the jumps are elite. If there is no $t$, we know that because all jumps are elite by definition Consider a sequence $b_n=a_n-vn$. Note that an elite jump doesn't change it. Thus from some point all the values of $b_n$ will come from a fixed set, take this set with minimal cardinality. Fix this big enough moment. Consider all the current chains in our system. In every chain the value of $b$ is fixed and will never change now. Now unite all chains with the same value of $b$ in the same group. Consider the group with minimal value of $b$. Then $b_{n-l_i} \leq b_n$, but $b_n$ is minimal, so all $n-l_i$ are from this group. A famous theorem states that by adding $l_1,\ldots,l_m$ we can get all numbers from some point, that are divisible by $gcd(l_1,\ldots,l_m)=d$. Ok, so from some point all numbers with a certain residues mod $d$ are from this minimal group. Now consider the second smallest group. $b_{n-l_i} \leq b_n$, but because $l_i \vdots d$, $b_{n-l_i}$ cant be from the smallest group. Then from some point the smallest group has certain residues mod $d$, e.t.c until the biggest group Now to finish out proof, note that because $l_1 \vdots d$, $b_n=b_{n-l_1}$ for any big enough $n$, but this rewrites as $$a_n=a_{n-l_1}+a_{l_1}$$