Call $ d_1,d_2$ the differences in the arithmetic progressions $ s_{s_i}$ and $ s_{s_i+1}$. Then, since $ s_i$ is increasing, \[ s_{s_1+1}+(n-1)d_1>s_{s_1}+(n-1)d_1=s_{s_n}\geq s_{s_{n-1}+1}=s_{s_1+1}+(n-2)d_2,\] or for all $ n$, $ d_1>(n-2)(d_2-d_1)$. If $ d_2>d_1$, we reach an easy contradiction when $ n$ grows without bounds. Similarly, \[ s_{s_1+1}-s_{s_1}=s_{s_n+1}-s_{s_n}+(n-1)(d_1-d_2)>(n-1)(d_1-d_2),\] again reaching an easy contradiction if $ d_1>d_2$. Hence $ d_1=d_2=d$ is the common difference between both arithmetic progressions, and $ s_{s_n+1}-s_{s_n}=s_{s_1+1}-s_{s_1}=D$ is constant for all $ n$.

daniel73 wrote: Hence $ d_1 = d_2 = d$ is the common difference between both arithmetic progressions, and $ s_{s_n + 1} - s_{s_n} = s_{s_1 + 1} - s_{s_1} = D$ is constant for all $ n$. This doesn't solve the problem though it might be an intermediary step.

Valentin Vornicu wrote: This doesn't solve the problem though it might be an intermediary step. That's the idea, I am still working on finishing up the problem using this intermediate step, maybe someone beats me to the answer using this first step. After all, this is not the contest, and I think collaborative efforts are OK... It's true that what I wrote may seem fairly obvious, but I'll be glad if it helps someone out there working on this problem...

Let $ d$ be a common difference of $ \{ s_{s_{i}} \}$. Since $ \{ s_{i} \}$ is a strictly increasing sequence, it is obvious that $ |k - l|\leq|s_{k} - s_{l}|$ for all natural numbers $ k,l$. Therefore, $ |s_{i + 1} - s_{i}| \leq |s_{s_{i + 1}} - s_{s_{i}}| = d$ $ \forall i \in N$. Thus, $ |s_{s_{i} + 1} - s_{s_{i}}|\leq d$. Therefore, a common difference of $ \{ s_{s_{i} + 1} \}$ is $ d$ as well. It indicates that for all positive integer $ i$, there exists a constant $ c$ such that $ s_{s_{i} + 1} = s_{s_{i}} + c$. Also, we know that a set of possible values of difference between two consecutive terms is both upper and lower bounded. Let $ m$ and $ M$ be the maximum and the minimum value of the differences. Then, there exist positive integers $ m'$ and $ M'$ satisfying $ s_{M' + 1} - s_{M'} = M$ and $ s_{m' + 1} - s_{m'} = m$. Since $ s_{s_{M' + 1}} - s_{s_{M'}} = d$ and $ s_{s_{M'} + M} = s_{s_{M' + 1}}$, $ s_{s_{M'} + M} - s_{s_{M'}} = d$. By the definition, $ mM \leq s_{s_{M'} + M} - s_{s_{M'}}\leq M^{2}$. Therefore, $ mM \leq d \leq M^{2}$. Using the same logic for $ m'$, we also can derive that $ m^{2} \leq d \leq mM$. Combining two inequalities, $ d = mM$. Therefore, all consecutive differences between $ s_{s_{M'} + M}$ and $ s_{s_{M'}}$ are $ m$, and those between $ s_{s_{m'} + m}$ and $ s_{s_{m'}}$ are $ M$. Therefore, $ s_{s_{M'} + 1} - s_{s_{M'}} = m = c$. In the same way, $ M = c$. Therefore, $ m = M$, which implies that $ \{ s_{i} \}$ is an arithmetic progression.

Note that $ \displaystyle s_{s_{k}+1}-s_{s_k}=s_{s_1+1}-s_{s_1}\geq s_{s_{k}+1}-s_{s_{k-1}+1}=r$.Also we have that $ s_{s_{1}+1}-s_{s_{1}}\leq s_{s_2}-s_{s_1}=r$.Now the conclusion is $ s_{s_1+1}-s_{s_1}=r$ where $ r$ the ratio of the arithmeticprogression.The conclusion is that $ s_{k+1}=s_{k}+1$.

Maybe then consider ${ s_{s_{s_{n} + 1}}} - s_{s_{s_{n}}} = d$ and also $ s_{s_{s_{n}} + 1} - s_{s_{s_{n}}} = d$ or maybe I am doing something wrong ; but first equation is useful I think... Edit: yeah, I was wrong, it's ${ s_{s_{s_{n} + 1}}} - s_{s_{s_{n}}} = d$; $ s_{s_{s_{n}} + 1} - s_{s_{s_{n}}} = D$; then $ s_{s_{s_{n}} + d} - s_{s_{s_{n}}} = D$, maybe this can lead to something...

I'll define ${ s_{s_{i+1}}-s_{s_i}}=A$, $ s_{s_{i+1}+1}-s_{{s_i}+1}=B$, $ s_{s_{i+1}+1}-s_{s_{i+1}}=d$. First, we can show $ A=B$. If not, $ s_{s_{i+1}+1}-s_{s_{i+1}}$ is a strictly decreasing or increasing sequence, both makes contradiction. (It's trivial to prove nondecreasing and if $ s_{s_{i+1}+1}-s_{s_{i+1}}$ is increasing sequence, there is a number j such that $ s_{s_{j+1}+1}-s_{s_{j+1}} > B$, but this is a contradiction. Then, $ d$ is a constant. Suppose that $ s_{i+1}-s_{i} = m$. Then, $ s_{s_{i+1}}-s_{{s_i}}= s_{s_{i}+m}-s_{{s_{i}}}=B$. This means if $ \min (s_{i+1}-s_{i}) =(s_{z+1}-s_{z}) J$, then $ \max (s_{i+1}-s_{i}) \leq B/J$ If $ B/J$ is not an integer, for pigeonhole principle, there is an integer $ s_{z} \leq Y < s_{z+1}$ such that $ s_{Y+1} -s_{Y} > B/J$. So $ B/J$ is an integer, and there is a real example for this maximum bound. Then, all number for $ s_{z} \leq Y < s_{z+1}$ , $ s_{Y+1} -s_{Y} = B/J$. And, all number for $ s_{s_{z}} \leq Z < s_{s_{z+1}}$, $ s_{Z+1} -s_{Z} = J$. Repeating similar process, for all $ K$, we can find $ K$ consecutive numbers such that $ s_{i+1} -s_{i} = J$. Also, we can find $ K$ consecutive numbers such that $ s_{i+1} -s_{i} = B/J$ It's easy to prove $ d \leq B$, and we can let $ K>B$, then we can find $ s_{N}$ in K consecutive numbers. Then, $ s_{s_{N}+1} -s_{s_{N}} = J$. So, $ d=J$. Similar way, we can prove $ d=B/J$. So, $ J=B/J$, which shows that the sequence is itself an arithmetic progression. Sorry for my bad English.

I think the idea to solve this problem is too easy to be an idea of 3rd problem. Is there any trap or something deceptive in the problem?

My idea is to see the sequence as if it were a function. The sequence is f(1), f(2),… I prove that f(n) is an arithmetic sequence using only that f(f(n)) is an arithmetic sequence. I looked for a mistake, but I didn’t found it. Please someone correct me. Let $ f(f(n) = a + dn$ Let $ g_{m}$=f(f(…f(n)…)) (m iterations of f) for a fixed n Then $ g_{m + 2} = dg_{m} + a$ Then $ g_{m} = w(\sqrt {d})^m + u( - \sqrt {d})^m - \frac {a}{d - 1}$ w and u are constants that satisfy w>u≥0 , that's because f is increasing Then $ f(n) = g_{1} = (w - u)\sqrt {d} - \frac {a}{d - 1}$ and $ n = (w + u) - \frac {a}{d - 1}$ Then $ f(n) + \frac {a}{d - 1}\leq(n + \frac {a}{d - 1})\sqrt {d}$ But this is true for every value of n Then $ f(f(n)) + \frac {a}{d - 1}\leq(f(n) + \frac {a}{d - 1})\sqrt {d}\leq(n + \frac {a}{d - 1})d$ Then $ f(f(n))\leq(a + dn) = f(f(n))$ Then the inequalities are equalities and then $ f(n) + \frac {a}{d - 1} = (n + \frac {a}{d - 1})\sqrt {d}$ Then $ f(n) = n\sqrt {d} + c$ (c is a constant) Then f(n) is an arithmetic sequence

Why can't $ u$ be negative? The sequence $ f(n)=4 * 5^n - (-5)^n$ is still increasing...

m.candales wrote: Then $ g_{m + 2} = dg_{m} + a$ Then $ g_{m} = w(\sqrt {d})^m + u( - \sqrt {d})^m - \frac {a}{d - 1}$ w and u are constants that satisfy w>u≥0 , that's because f is increasing I don't think this is correct. In fact it seems that $ g_{2m} = d^{2m} \left( \frac a{d - 1} + n \right) - \dfrac a{d - 1}$, if we consider $ g_0 =n$ ...

u doesn't have to be non-negative; I was wrong asuming that

This was an amusing little problem, but it seems like day 1 was overall quite easy

I've tried to rewrite this problem into: Suppose there exists a function $ f: Z^ + \rightarrow Z^ +$ is strictly increasing and $ f(a(x - 1) + b) = a(f(x) - 1) + b$ for all integers x, where a and b are positive integers. Show that f is linear. But now it's very late, and I haven't solved it yet . Could anyone help me?

What does $ \mathbb Z ^+$ mean?

Valentin Vornicu wrote: What does $ \mathbb Z ^ +$ mean? Um.. i guess positive integers

The way I'd do it: As daniel73 wrote, let $ d$ be the common difference of the two arithmetic progressions. Also let $ a=s(s_i+1)-s(s_i)$ be the difference between the two. For notation's sake, we use $ s(k)$ interchangeably with $ s_k$ and denote the $ n$-fold composition $ s^n$. Note that since any $ [i,i+1]$ (for large enough $ i$) belongs to some $ [s(j),s(j+1)]$, we must have $ s(i+1)-s(i)\le s(s(j+1))-s(s(j))=d$, and the differences of $ s$ are bounded above. Suppose that for some $ j$, $ s(j+1)-s(j)=a_1>a$. Then $ s^2(j+1)-s^2(j)=d$, and $ s^3(j+1)-s^3(j)=\sum_{k=s(j)}^{s(j+1)-1}s^2(k+1)-s^2(k)=a_1\cdot d$ (each of the $ a_1$ terms is $ d$). Arranging that sum differently, $ a_1\cdot d=\sum_{k=s^2(j)}^{s^2(j+1)-1}s(k+1)-s(k)$, and the average of those $ d$ terms is $ a_1$. One of them ($ s(s^2(j)+1)-s(s^2(j))$) is equal to $ a<a_1$, so at least one term $ s(j_1+1)-s(j_1)=a_2$ must be strictly larger than $ a_1$. With $ a_1$ an integer, we have $ a_2\ge a_1+1$. Repeat this process; among the $ k\in[s^{2n}(j),s^{2n}(j+1))$, there is some $ j_n$ with $ s(j_n+1)-s(j_n)=a_{n+1}\ge a_1+n$. For large enough $ n$, this is greater than $ d$, a contradiction. Similarly, what if some difference $ a_1$ is less than $ a$? Again, $ s^3(j+1)-s^3(j)=\sum_{k=s(j)}^{s(j+1)-1}s^2(k+1)-s^2(k)=a_1\cdot d$ and $ a_1\cdot d=\sum_{k=s^2(j)}^{s^2(j+1)-1}s(k+1)-s(k)$. The average of those $ d$ terms is $ a_1$ and one is $ a>a_1$, so another must be $ <a_1$. We get some $ j_n\in [s^{2n}(j),s^{2n}(j+1))$ with $ s(j_n+1)-s(j_n)=a_{n+1}\le a_1-n$. This is eventually $ \le 0$, which contradicts the increasing nature of the sequence. We can't have any difference either greater than or less than $ a$, so $ s$ is an arithmetic progression with common difference $ a$. As a final note, we do need both arithmetic progressions. If we merely have that $ s^2$ is an arithmetic progression, examples like the following are possible: (0-9 across, by tens in each row) $ \begin{tabular}{cccccccccc}1&3&6&9&11&13&15&17&19&21\\24&27&30&33&36&39&42&45&48&51\\54&57&59&61&63&65&67&69&71&73\\75&77&79&81&83&85&87&89&91&93\end{tabular}$ There are blocks of differences of two and three, and $ s^2$ has common difference six.

First, it's easy to prove $ s_{s_1}, s_{s_2}, \ldots$ and $ s_{s_1+1}, s_{s_2+1}, \ldots$ have the same common difference: just note that the sequences $ s_{s_i+1}-s_{s_i}$ and $ s_{s_{i+1}}-s_{s_i+1}$ are positive arithmetic sequences whose common differences add to zero, and thus they must both be constant. So let $ s_{s_2}-s_{s_1}=d$. Now we have $ s_{i+1}-s_i \le s_{s_{i+1}}-s_{s_i}=d$, and hence $ s_{i+1}-s_i$ is bounded. So it achieves a maximum $ s_{a+1}-s_a=M$ and minimum $ s_{b+1}-s_b=m$. Note \[ s_{s_{s_{a+1}}}-s_{s_{s_a}}=d(s_{a+1}-s_a)\] because $ s_{s_1}, s_{s_2}, \ldots$ is an arithmetic sequence with common difference $ d$. \[ =dM=(s_{s_{a+1}}-s_{s_a})M\] Since $ M$ is the maximum of $ s_{i+1}-s_i$, and the average value of $ s_{i+1}-s_i$ from $ s_{\left(s_{s_a}\right)}$ to $ s_{\left(s_{s_{a+1}}\right)}$ is $ M$, it follows $ s_{s_{s_a}+1}-s_{s_{s_a}}=M$. But remember $ s_{s_i+1}-s_{s_i}$ is constant, so it equals $ M$. By a similar argument using that $ m$ is the minimum of $ s_{i+1}-s_i$, we have $ s_{s_i+1}-s_{s_i}=m$. Hence $ M=m$ and we are done.

Let difference of a given arithmetic progression be D. First we prove $ s_{s_{i}+1}-s_{s_{i}}$ is constant ( Or the difference of first progression is difference of second). Then : Let i be an integer for which $ s_{i+1}-s_{i}$ is minimal. For $ j=s_{i}$ , $ j=s_{i}+1$ ... $ j=s_{i+1}-1$ Sum of all $ s_{j+1}-s_{j}$ is D , so there exists j such that : $ s_{j+1}-s_{j}\ge\frac{D}{s_{i+1}-s_{i}}$ For $ k=s_{j}$ , $ k=s_{j}+1$ ... $ k=s_{j+1}-1$ Sum of all $ s_{k+1}-s_{k}$ is D , so there exists k such that : $ s_{k+1}-s_{k}\le\frac{D}{s_{j+1}-s_{j}}$ So $ s_{k+1}-s_{k}\le{s_{i+1}-s_{i}}$ We know $ s_{i+1}-s_{i}$ is minimal , so $ s_{k+1}-s_{k}={s_{i+1}-s_{i}}$ For every k in {$ s_{j}$ , ... , $ s_{j+1}-1$} and $ s_{j+1}-s{j}=\frac{D}{s_{i+1}-s_{i}}$ For every j in {$ s_{i}$ , ... , $ s_{i+1}-1$} So : $ s_{s_{i}+1}-s_{s_{i}}=\frac{D}{s_{s_{j}+1}-s_{s_{i}}}$ we know $ s_{s_{i}+1}-s_{s_{i}}=s_{s_{j}+1}-s_{s_{i}}$ so it is equal to $ \sqrt{D}$ If minimal is equal to $ \sqrt{D}$ , every is equal to $ \sqrt{D}$. so , s is an arithmetic progression.

The first claim is that the sequences $\{s_{s_i}\}$ and $\{s_{s_i+1}\}$ have the same common difference. Note that the sequence $\{s_{s_i+1}-s_{s_i}\}$ is an arithmetic sequence as it is the difference of two arithmetic sequences. It must also have a nonnegative common difference, as otherwise we would eventually have $s_{s_i}>s_{s_i+1}$, contradicting that $\{s_i\}$ is increasing. But we have that $s_{s_{s_k}+1}-s_{s_{s_k}}\le s_{s_{s_k+1}}-s_{s_{s_k}}$ is the common difference of $\{s_{s_i}\}$, so $\{s_{s_{s_i}+1}-s_{s_{s_i}}\}$ is bounded above, implying that $\{s_{s_i+1}-s_{s_i}\}$ is also bounded above. This means that it is constant, so $\{s_{s_i}\}$ and $\{s_{s_i+1}\}$ have the same common difference, as desired. Let this common difference be $d$, and let $c=s_{s_i+1}-s_{s_i}$, which is the fixed difference between $\{s_{s_i}\}$ and $\{s_{s_i+1}\}$. Now, we claim that $\{s_{i+1}-s_i\}$ is bounded above. Indeed, if $k$ is the unique integer such that $i\in[s_k,s_{k+1})$, then we have that $s_{i+1}-s_i\le s_{s_{k+1}}-s_{s_k}=d$, as desired. Now, let $M$ and $m$ be the maximum and minimum value of $\{s_{i+1}-s_i\}$ over all positive integers $i$. Suppose that $k$ is a positive integer such that $s_{k+1}-s_k=M$. Then, we have that $c+(M-1)m\le s_{s_k+1}-s_{s_k}+\sum_{i=s_k+1}^{s_k+M-1}(s_{i+1}-s_i)\le c+(M-1)M$, so $d-c\in[Mm-m,M^2-M]$ as the middle sum is simply $s_{s_{k+1}}-s_{s_k}$. Similarly, if $k$ is a positive integers such that $s_{k+1}-s_k=m$, then we have that $c+(m-1)m\le s_{s_k+1}-s_{s_k}+\sum_{i=s_k+1}^{s_k+m-1}(s_{i+1}-s_i)\le c+(m-1)M$. This implies that $d-c\in[m^2-m,Mm-m]$. As $m\le M\implies m^2-m\le Mm-M\le Mm-m\le M^2-M$, we must have that $m=M$ in order for the intervals $[Mm-m,M^2-M]$ and $[m^2-m,Mm-M]$ to intersect. But this then implies that the sequence $\{s_{k+1}-s_k\}$ is constant, so $\{s_k\}$ is an arithmetic sequence, as desired.

Wait, does this actually work? If so, then it's a very nice problem! IMO 2009/3 wrote: Suppose that $ s_1,s_2,s_3, \ldots$ is a strictly increasing sequence of positive integers such that the sub-sequences \[s_{s_1},\, s_{s_2},\, s_{s_3},\, \ldots\qquad\text{and}\qquad s_{s_1+1},\, s_{s_2+1},\, s_{s_3+1},\, \ldots\]are both arithmetic progressions. Prove that the sequence $ s_1, s_2, s_3, \ldots$ is itself an arithmetic progression. Proposed by Gabriel Carroll, USA

Nice problem . Rephrase the problem with the flavour of functional equations: Quote: Suppose $f : \mathbb{N} \to \mathbb{N}$ is a strictly increasing function such that \[ f(f(1)), f(f(2)), f(f(3)), \dots \ \ \text{and} \ \ f(f(1) + 1), f(f(2) + 1), f(f(3) + 1) \]are both arithmetic progressions. Prove that $f(1), f(2), f(3), \dots$ is itself an arithmetic progression. Now, we have for any integer $a,n,m \in \mathbb{N}$. Let \[ f(f(n)) = f(f(m)) + a(n - m) \]\[ f(f(n) + 1) = f(f(m) + 1) + b(n - m) \] Claim 01. $a = b$ Proof. Since $f$ is strictly increasing, we have \[ (a - b)(n - m) < f(f(m) + 1) - f(f(m)) \]And since $(a - b)(n - m)$ is bounded from above and $n - m$ could grow sufficiently large. We must have $a \le b$. Now, we know that $f(n + 1) \ge f(n) + 1$, since $f$ is strictly increasing. Therefore, \[ f(f(n + 1)) \ge f(f(n) + 1) \]\[ f(f(1)) + an \ge f(f(1) + 1) + b(n - 1) \]\[ an - bn + b \ge f(f(1) + 1) - f(f(1)) > 0 \]\[ (a - b)n + b > 0 \]\[ b > (b - a)n \]Notice that we have $b \ge a$, and $n$ could grow sufficiently large. Therefore, it is clearly a contradiction for $b > a$. Hence, we must have $b = a$. Claim 02. $f(n) - f(m) \le (n - m)a$ for any $n,m \in \mathbb{N}$ Proof. Notice that for $n > m$, we have \[ f(f(n)) = f( f(m) + f(n) - f(m) ) \ge f(f(m)) + f(n) - f(m) \]Thus, \[ (n - m)a = f(f(n)) - f(f(m)) \ge f(n) - f(m) \] Define $d_n = f(n + 1) - f(n)$, now Claim 03. $d_{f(f(n))} = d_n$ for all $n \in \mathbb{N}$. Proof. From Claim 02, $d_n$ is bounded above by $a$. For simplicity, let $f(f(n)) = Dn + x$ and $f(f(n) + 1) = Dn + y$. Take $k$ that maximizes the value of $d_k$. Now, consider counting $f(f(f(n + 1))) - f(f(f(n)))$ in two ways. Then, we have \[ f(Dn + D + x) - f(Dn + x) = D( f(n + 1) - f(n) ) = D \cdot d_n \]\[ \sum_{i = 0}^{D - 1} f(Dn + x + i + 1) - f(Dn + x + i) = D \cdot d_n \]\[ \sum_{i = 0}^{D - 1} d_{Dn + x + i} = D \cdot d_n \]Since we choose that $d_n$ is maximum over all possible $d_i$s, then we must have \[ d_{Dn + x} = d_{Dn + x + 1} = \dots = d_{Dn + x + D - 1} = d_n \]and therefore, we have $d_n = d_{Dn + x} = d_{f(f(n))} = f( f(f(n)) + 1) - f(f( f(n))) = y - x $ for all $n \in \mathbb{N}$. Therefore, $f(n)$ is an arithmetic progression as well. Al fine ~

For ease of notation, we replace $s_n$ with $f(n)$. Then $f$ is a strictly increasing function from $\mathbb{Z}_+$ to $\mathbb{Z}_+$ such that $f(f(1)),f(f(2)),f(f(3)),\dots$ and $f(f(1)+1),f(f(2)+1),f(f(3)+1),\dots$ are arithmetic progressions. Let $f(f(2))-f(f(1)) = d_1$ and $f(f(2)+1)-f(f(1)+1) = d_2$. We claim that $d_1 = d_2$. Proof: Suppose $d_1 \ne d_2$. We split this into two cases: $d_2 < d_1$ and $d_1 < d_2$. Suppose that $d_2 < d_1$. We note that for sufficiently large $N$, \[f(f(N)+1)-f(f(1)+1) = (N-1)d_2 \le (N-2)d_1 = f(f(N))-f(f(2)).\]But this is absurd because $f(f(N)) < f(f(N)+1)$ and $f(f(2)) > f(f(1))$. Now, suppose that $d_1 < d_2$. For sufficiently large $N$, we have that \[f(f(N))-f(f(1)) = (N-1)d_1 \ge (N-2)d_2 = f(f(N-1)+1) - f(f(1)+1).\]Again, this absurd because $f(f(N)) \ge f(f(N-1)+1)$ and $f(f(1)) < f(f(1)+1)$. Thus, neither $d_1 < d_2$ nor $d_2 < d_1$ holds, meaning that $d_1 = d_2$. $\blacksquare$ We let $d_1 = d_2 = d$. Thus, for all $n$, some $r_1$, and some $r_2$, we have that $f(f(n)) = dn+r_1$ and $f(f(n)+1)=dn+r_2$. For all $n$, we then have that $f(f(n)+1)-f(f(n)) = r_2-r_1$. Consider the sequence \[f(2)-f(1),f(3)-f(2),f(4)-f(3),\dots \qquad (1).\]By the well-ordering principle, this sequence has a minimal element $m$. Lemma: The greatest element $k$ of sequence $1$ exists and satisfies $d \ge km$. Proof: Consider any element $k$ of sequence $1$. Since $k$ is an element of this sequence, it can be expressed as $f(a+1)-f(a)$ for some $a$. We have that $f(f(a+1))-f(f(a)) = d$. We rewrite this as \[d = \sum_{i=0}^{k-1} \left(f(f(a)+i+1)-f(f(a)+i)\right) \ge \sum_{i=0}^{k-1} m = km,\]and we are done. $\blacksquare$ Since $m$ is an element of sequence $1$, there exists some $b$ such that $f(b+1)-f(b) = m$. Now, we observe that \[d=f(f(b+1))-f(f(b)) = \sum_{i=0}^{m-1} \left(f(f(b)+i+1)-f(f(b)+i)\right) \le km.\]But we already have that $d \ge km$, so we see that $d = km$. Now, we return to the $a$ defined in our lemma to see that because equality holds, we must have that $f(f(a)+i+1)-f(f(a)+i) = m$ for all $0 \le i < k$. In particular, we have that $r_2-r_1 = f(f(a)+1)-f(f(a)) = m$. Now, since $d = km$, we also have that $f(f(b)+i+1)-f(f(b)+i) = k$ for all $0 \le i < m$. In particular, this shows that $r_2 - r_1 = f(f(b)+1)-f(f(b)) = k$. But this means that $k = m$. Since $k$ is the greatest element of sequence $1$ and $m$ is the least element of sequence $1$, we see that sequence $1$ is constant. So, we see that for all $n$, we have \[f(n)-f(1) = \sum_{i=1}^{n-1} \left(f(i+1)-f(i)\right) = (n-1)m,\]implying that $f$ is the arithmetic progression $f(n) = (n-1)m + f(1) = nm + f(1)-m$. We are done. $\blacksquare$

Rephrase this as a functional equation $f:\mathbb{N}\to\mathbb{N}$, where $f(x)=s_x$. Let $f(f(x))=ax+b$ where $a\ge 1$ and $b\ge 0$. Since $f$ is increasing, we have \[ax+b=f(f(x))<f(f(x)+1)\le f(f(x+1))=ax+b+a,\]so in fact, \[f(f(x)+1) = ax+b+c\]where $1\le c\le a$. Note that \[f(ax+b)=f(f(f(x))) = af(x)+b\]and \[f(ax+b+c) = f(f(f(x)+1))=a[f(x)+1]+b.\]Call $L$ good if $f(x+1)\ge f(x)+L$ for all $x$. We see that $1$ is good. Lemma: If $L$ is good, then so is $1+\lceil L(1-c/a)\rceil$. Proof: Indeed, we have \[af(x+1)+b=f(a(x+1)+b)\ge L(a-c)+f(ax+b+c) = L(a-c)+a[f(x)+1]+b,\]so \[f(x+1)\ge L\frac{a-c}{a}+1+f(x),\]so the desired result follows. $\blacksquare$ Clearly, all large enough numbers are not good, so let $L$ be the largest good number. Now, if $L<a/c$, then \[L(1-c/a)=L-(c/a)L>L-1,\]so by the lemma, there is a larger good number. Thus, $L\ge a/c$. If $L>a/c$, then \[a+af(x)+b=f(ax+b+c)\ge cL+f(ax+b)>a+af(x)+b,\]which is a contradiction, so $L=a/c$. In fact, the above implies that $f(ax+b+1)=f(ax+b)+a/c$, else we get a similar contradiction. Thus, \[af(x)+b+a/c = f(ax+b+1)=f(f(f(x))+1)=af(x)+b+c,\]so $a/c=c$, so $c^2=a$. So to summarize, we have \[f(f(x))=c^2x+b\]and $f(x+1)\ge f(x)+c$. This is actually enough to finish. Call $x$ normal if $f(x+1)=f(x)+c$, and weird otherwise. Claim: There are only finitely many weird numbers. Proof: Suppose to the contrary. Then, for any $N$, we have \[f(x)\ge f(1)+c(x-1)+N\]for large enough $x$. Thus, for large enough $x$, we have \[c^2x+b=f(f(x))\ge f(1)+c(f(1)+c(x-1)+N-1)+N = c^2x+g(N),\]where $g$ is an increasing function of $N$. This is clearly a contradiction, so the claim is proved. $\blacksquare$ Thus, all large enough numbers are normal, so $f(x)=cx+d$ for large enough $x$. We see that $c(cx+d)+d=c^2x+b$ for large enough $x$, so $b=d(c+1)$. Redefine normal $x$ such that $x$ is normal if and only if $f(x)=cx+d$. Note that if $f(x)$ is normal, then \[c^2x+d(c+1) = f(f(x)) = cf(x)+d,\]so $f(x)=cx+d$, so $x$ is normal. Thus, every $x$ is normal, since eventually $f^n(x)$ is normal for large enough $x$. Thus, $f(x)=cx+d$ for all $x$ as desired. Remark: Once I got $f(ax+b)=af(x)+b$ and $f(ax+b+c)=af(x)+b+a$, I felt I should be able to use these and increasing to get quite strong conditions. Indeed, I let $a=5$, $b=0$, $c=2$, and tried to construct a single sequence satisfying just these two conditions. Everything I tried eventually contradicted increasing, and when I dug deeper as to why, the lemma fell out naturally. The rest of the solution given the lemma was quite easy.

Let \(a_i=s_i-s_{i-1}\) for \(i \ge 2\) and \(a_1=s_1\). Note that \(a_i \ge 1\) for all \(i\), and \(s_i=a_1+\ldots+a_i\). We are given \[a_{s_i+1}+a_{s_i+2}+\ldots+a_{s_{i+1}}=c_1\]for some constant \(c_1\), and \[a_{s_i+2}+a_{s_i+2}+\ldots+a_{s_{i+1}+1}=c_2\]for some constant \(c_2\). Lemma: \(c_1=c_2,\) or \(a_{s_i+1}\) is constant. Proof: Assume by contradiction \(c_2 \neq c_1\). Note \(a_{s_{i+1}+1}-a_{s_i+1}=c_2-c_1\), so by induction on \(i\), \(a_{s_i+1}\) is unbounded, which is impossible since the value must always be between \(1\) and \(c_1\). Thus \(c_1=c_2\). \(\blacksquare\) Now, define the constant \(c_3=a_{s_i+1}\). Note that for every \(i\), we have \[1 \le a_i \le a_{s_i+1}+a_{s_i+2}+\ldots+a_{s_{i+1}} = c_i,\]wwith the second inequality following from each term on the RHS being at least \(1\). Thus, \(a_i\) is bounded. Let \(k,l\) be integers so that \(a_k \ge a_i \ge a_l\) for all integers \(i\). Main claim(which finishes the problem): \(a_k=c_3\) and \(a_l=c_3\). Proof: Let \(S_i\) denote the sum \(a_{s_i+1}+a_{s_i+2}+\ldots+a_{s_{i+1}}\). Note \(S_i\) has value \(c_1\) and has a total of \(a_i\) terms. Now, the sum \[S_{s_k+1}+S_{s_k+2}+\ldots+S_{s_{k+1}}\]has a total of \((a_{s_k+1}+\ldots+a_{s_{k+1}})=c_1\) terms, and contains \(s_{k+1}-s_k=a_k\) sub-sums, each with value \(c_1\). Thus, the value and number of terms of the sum are \(a_kc_1\) and \(c_1\) terms, respectively. But since each term is at most \(a_k\) , all terms are in fact equal to \(a_k\). In particular, \[a_k=a_{s_{s_k+1}+1}=c_3,\]so \(a_k=c_3\) as desired. \(a_l=c_3\) follows analogously. \(\blacksquare\) Since the maximum and minimum of \(a_i\) are the same, then \(a_i\) is constant, and \(s_i\) forms an arithmetic sequence as desired.

Translating into functional equation language, we have an increasing function $f:\mathbb{N}\to\mathbb{N}$ such that both \[f(f(1)),f(f(2)),f(f(3)), \dots \text{ and } f(f(1)+1),f(f(2)+1),f(f(3)+1),\dots\]are arithmetic progressions. Observe that \[f(1) < f(1)+1\le f(2) < f(2)+1 \le f(3) < f(3)+1 \le \dots\]so \[f(f(1)) < f(f(1)+1) \le f(f(2)) < f(f(2)+1) \le f(f(3)) < f(f(3)+1) \le \dots\]This means that the two arithmetic progressions have the same common difference, say $N$. Define $g(x) = f(x+1)-f(x)$ for each $x\in\mathbb{N}$. Let $n = g(f(1)) = g(f(2)) = \dots$ and furthermore define $m = \min_{x\in\mathbb{N}} g(x)$, $M=\sup_{x\in\mathbb{N}} g(x)$. The goal is to prove that $m=M$. First, we know that $g(x) = f(x+1)-f(x) \le f(f(x+1)) - f(f(x)) = N$, so $M$ is a positive integer. Now, take $x$ such that $g(x) = m$. Then \[x\to f(x) \to f(f(x)),\ x+1\to f(x)+m \to f(f(x))+N\]This means that $\frac{N}{m} \le M$ by pigeonhole. On the other hand, take $x$ such that $g(x) = M$, then \[x\to f(x) \to f(f(x)),\ x+1\to f(x)+M \to f(f(x))+N\]This means that $\frac{N}{M}\ge m$ by pigeonhole. This implies that $mM \ge N \ge mM$, so equality is achieved. This means that $f(f(x)+1) = f(x) + n = f(x) + m$ in the first case, and $f(f(x)+1) = f(x) + n = f(x) + M$ in the second case, so $m = n = M$ as desired.

First, note that both the given subsequences must have the same common difference. To see this, let $s_{s_i} = a + xi$ and $s_{s_{i}+1} = b + yi$ with $x,y$ as the common differences. If $x > y$, then pick $i$ sufficiently large so that $s_{s_i} > s_{s_i+1}$. If $y > x$, then again take $i$ sufficiently large so that we have $s_{s_{i}+1} > s_{s_{i+1}}$, which are both contradictions. Let $d$ be the common common difference of the $2$ subsequences.

Notice that we have $d = s_{s_{i+1}}-s_{s_i} \ge (s_{i+1}-s_{i})S$ since there are at least those many terms in between and each difference is at least $S$. Similarly, we have that $d = s_{s_{j+1}}-s_{s_j} \le (s_{j+1}-s_{j})L$ So, we have $(s_{i+1}-s_i)S \le d \le (s_{j+1}-s_{j})L$. But, since we have this true for any $i,j$, pick them such that maximum is achieved on LHS and minimum on RHS. This forces $LS \le d \le LS$ and so we have $d = LS$ Assume now, ftsoc that $L > S$ We shall now use the following scam idea. Consider the first $i$ such that $s_{i+1} - s_i$ is either $L$ or $S$. WLOG assume its $S$ since the other thing is similar. We have that all terms in between $s_{s_{i+1}}-s_{s_{i}}$ differ by $L$. But since we had $s_{s_{i+1}+1} - s_{s_{i}+1} = d = s_{s_{i+1}} - s_{s_{i}}$, which since $s_{s_{i}+1} = s_{s_{i}} + L$, means that $s_{s_{i+1}+1} = s_{s_{i+1}} + L$. Similarly, we obtain that $s_{s_{i+k}+1} = s_{s_{i+k}} + L$ for all $k \ge 1$. Now, consider the first $j$ such that $s_{j+1}-s_j = L$, obviously $j > i$ since that's how we defined it. But now, all terms between $s_{s_{j+1}}$ and $s_{s_{j}}$ must differ by $S$. But this is impossible! Because we had that $s_{s_{i+k}+1} = s_{s_{i+k}} + L$ and so there is at least one pair of consecutive terms that differs by $L$ and so u can never have all of them differing by $S$. Therefore, we have that $L = S$ and so $s_{i+1} - s_i$ is constant and so it is indeed an arithmetic progression, as desired. $\blacksquare$

Let $S$ be the sequence $s_1, s_2, \ldots$, and let $S_1$ and $S_2$ be the subsequences $s_{s_1}, s_{s_2}, \ldots$ and $s_{s_1+1}, s_{s_2+1}, \ldots$ respectively. Define $x = s_{s_2}-s_{s_1} = s_{s_{i+1}}-s_{s_i}$ and $y = s_{s_1+1}-s_{s_1} = s_{s_i+1}-s_{s_i}$ for all positive integers $i$. Claim: Let $m = \min(s_{i+1}-s_i), i \in \mathbb Z ^ +$. If $m < y$, then there does not exist a sequence $S$. Proof: Assume otherwise. Let $i$ be an index such that $s_{i+1}-s_i = m$. Notice that $s_{s_{i+1}}-s_{s_i+1} = x-y$ so for $j \in [s_i+1, s_{i+1}-1]$, the average value of $s_{j+1}-s_j$ is $\frac{x-y}{s_{i+1}-s_i-1} = \frac{x-y}{m-1}$. This means there exists some $k$ such that $s_{k+1}-s_k = \left\lceil\frac{x-y}{m-1}\right\rceil$. Now, we again have $s_{s_{k+1}}-s_{s_k+1} = x-y$, which means for $j \in [s_k+1, s_{k+1}-1]$, the average value of $s_{j+1}-s_j$ is $\frac{x-y}{s_{k+1}-s_k-1} \le \frac{x-y}{\left\lceil\frac{x-y}{m-1}\right\rceil-1} = M$. It suffices to show $M \le m$ with equality when $m = \frac{x-y}{m-1}$. Let $\left\lceil\frac{x-y}{m-1}\right\rceil = \frac{x-y}{m-1}+k$ for some nonnegative real $k$. Notice that $$\frac{x-y}{\left\lceil\frac{x-y}{m-1}\right\rceil-1} \le m \implies m\le m\left(\frac{x-y}{m-1}+k\right)-(x-y) \implies m \le \frac{x-y}{m-1}+mk.$$Notice that $x = s_{s_2}-s_{s_1+1}+s_{s_1+1}-s_1 \ge m(m-1)+y$, so substituting gives $$m \le \frac{m(m-1)+y-y}{m-1}+mk = m+mk$$with equality when $m = \frac{x-y}{m-1} \implies k = 0$. If equality doesn't exist, then we have that $M \le m-1$ which means there exists an index $p$ such that $s_{p+1}-s_p = m-1 < m$, a contradiction. We now tackle the equality case separately. Because $y > m = \frac{x-y}{m-1}$, we define $a = s_{s_1}$ and $b = s_{s_1+1}$, which gives us $s_b-s_{a+1} = x-y$, and that for $j \in [a+1, b-1]$, the average value of $s_{j+1}-s_j$ is $\frac{x-y}{b-a-1} = \frac{x-y}{y-1} = \frac{m(m-1)+y-y}{y-1} < m$. Therefore, there exists an index $k$ such that $s_{k+1}-s_k = m-1 < m$, a contradiction. $\square$ Notice that our claim is symmetric with the claim that if $y < n = \max(s_{i+1}-s_i), i \in \mathbb Z ^ +$, then there does not exist a sequence $S$. Therefore, all $s_{i+1}-s_i = y$ and thus $S$ is an arithmetic sequence. $\blacksquare$ Remarks: Cool bounding problem. I was kinda lazy at the end and saying it's "symmetrical" is not rigorous at all but the computation for the following is basically identical.

Redefine $(s_i)$ as $f(i)$. The problem condition is equivalent to $f(f(1)), f(f(2)), \ldots, $ and $f(f(1) + 1), f(f(2) + 1), \ldots, $ are arithmetic progressions and $f(1), f(2), \ldots, $ is strictly increasing. Claim: Both arithmetic sequences have the same common difference. Proof: Suppose not and their differences were equal to $d_1$ and $d_2$, respectively. So $f(f(n)) = d_1 n + e_1$ and $f(f(n) + 1) = d_2 n + e_2$ for some constants $e_1, e_2$. If $d_1 > d_2$, then there exists large $i$ such that $f(f(i)) > f(f(i) + 1),$ which is absurd since $f$ is strictly increasing. If $d_1 < d_2$, there exists large $i$ such that $f(f(i+1)) < f(f(i) + 1)$ (since $d_1 i + (d_1 + e_1) <d_2 i + e_2$ for large $i$). This implies that $f(i+1) < f(i) + 1$, so $f(i+1) \le f(i)$, contradiction. $\square$ Let the common differences be equal to $d$ and $g(n) = f(n+1) - f(n)$. We see that \[ d = f(f(n+1)) - f(f(n)) = g(f(n)) + g(f(n) + 1) + \cdots + g(f(n+1) -1) \ \ \ \ \ \ \ \ \ \ \ \ \ (1)\] Since every positive integer is in the interval $[f(n), f(n+1) - 1]$ for one positive integer $n$, so $g(x) \le d\forall x\in \mathbb{N}$. Since $g$ is upper (and obviously lower) bounded, we may let $c$ be the minimum value of $g$ and $C$ be the maximum. Let $g(m) = c$ and $g(M) = C$ for some positive integers $m, M$. Denote $g[a,b]$ for $a<b$ as $g(a) + g(a+1) + \cdots + g(b)$. Notice that $d = g[f(m), f(m+1) - 1]$, which is the sum of $g(m) = c$ values of $g$, and thus at most equal to $C\cdot c$. We see that $d$ is also equal to $g[f(M), f(M+1) - 1]$, which is the sum of $g(M) = C$ values of $g$, and thus at least equal to $c\cdot C$. Hence $c \cdot C \le d \le C\cdot c$, so $d = c\cdot C$. Claim: $g(f(i))$ is constant over all positive integers $i$. Proof: Note that \[ d = f(f(n+1) + 1) - f(f(n) + 1) = g(f(n) + 1) + g(f(n) + 2) + \cdots + g(f(n+1)) \]Comparing this with $(1)$ gives that $g(f(n)) = g(f(n+1))$, so $g(f(i))$ must be constant. $\square$ Now we have that the $c$ numbers $g(f(m)), g(f(m)+1), \ldots, g(f(m+1) - 1)$ are all at most $C$ and add up to $d = c\cdot C$, so they are all equal to $C$. Also, the $C$ numbers from $g(f(M)), g(f(M) + 1), \ldots, g(f(M+1) - 1)$ are all at least $C$ and add up to $d = C\cdot c$, so they are all equal to $c$. Therefore, $c = g(f(m)) = g(f(M)) = C$, which means $g$ is constant, so $f$ is an arithmetic sequence.

Let $D$ and $D'$ be the respective differences of the given arithmetic progressions, and for all $i$ let $d_i=s_{i+1}-s_i$. Because $s_i$ is strictly increasing, $D=s_{s_{i+1}}-s_{s_i} \geq s_{i+1}-s_i$, hence $d_i$ is bounded. Therefore, let $m$ and $M$ be its minimum and maximum respectively. By considering some $i$ with $d_i=M$, it follows that $\tfrac{D}{M} \geq m \implies D \geq mM$, else by expectation we can find some $d_j<m$. By considering some $i$ with $d_i=m$, it follows that $\tfrac{D}{m} \leq M \implies D \leq mM$. This means that $D=mM$, and similarly $D'=mM$, so $d_{s_i}$ is constant. On the other hand, due to equality considerations, if $d_i=M$, then $d_{s_i},d_{s_i+1},\ldots,d_{s_{i+1}-1}$ must all equal $m$, and if $d_j=m$, then $d_{s_j},d_{s_j+1},\ldots,d_{s_{j+1}-1}$ must all equal $M$. But since $d_{s_i}=d_{s_j}$, it follows that $M=m$, so $d_i$ is constant and hence $s_i$ is arithmetic. $\blacksquare$

Let $d_1=s_{s_{i+1}}-s_{s_i}$ and $d_2=s_{s_{i+1}+1}-s_{s_i+1}$. We present two claims. Claim: $d_1\geq d_2$. Proof. Notice that \[s_{s_{i+d_2}}-s_{s_i}=d_1d_2=s_{s_{i+d_1}+1}-s_{s_i+1}.\]Therefore, we have \[s_{s_{i+d_1}+1}-s_{s_{i+d_2}}=s_{s_i+1}-s_{s_i}>0 \iff s_{s_{i+d_1}+1}>s_{s_{i+d_2}}\]as the sequence is strictly increasing. Using this again, we get \[s_{i+d_2}<s_{i+d_1}+1\leq s_{i+d_1+1}\]and again to get $i+d_2<i+d_1+1$ or $d_1+1>d_2$ implying the claim. $\blacksquare$ Claim: $d_1=d_2$ Proof. Suppose $d_1-d_2\geq 1$. Then, subtracting $s_{s_{i+k}}-s_{s_i}=kd_1$ and $s_{s_{i+k}+1}-s_{s_i}=kd_2$ we obtain \[\left(s_{s_{i+k}}-s_{s_{i+k}+1}\right)+\left(s_{s_i+1}-s_{s_i}\right)=k\left(d_1-d_2\right)\geq k\]But $s_{s_{i+k}}-s_{s_{i+k}+1}$ is negative and $s_{s_i+1}-s_{s_i}$ is a constant, hence we get a contradiction with sufficiently large $k$. $\blacksquare$ Now, let $a_i=s_{i+1}-s_i$; the claim above gives $a_{s_i}$ is constant. Also, let $B\leq a_i\leq A$ so that $A$ and $B$ are both hit by $a_i$, which exist since clearly $a$ is bounded. Therefore, we have $d_1=\sum_{k=s_i+1}^{s_{i+1}}a_k$ so $a_i\cdot A\geq d_1 \geq a_i\cdot B$ implying $AB=d_1$ since there is some $a_i=A,B$. Then, for $a_i=A$, we have \[AB=d_1=\sum_{k=s_i+1}^{s_{i+1}}a_k\geq A\cdot B\]and hence all summands are equal to $B$, which forces $B=a_{s_{i+1}}=a_{s_i}=A$ as desired.

Let $d=s_{s_2}-s_{s_1}$ and $e=s_{s_2+1}-s_{s_1+1}$. Now let $t_i=s_{s_i+1}-s_{s_i}$. Note that $t_i\le s_{s_{i+1}}-s_{s_i}=d$ and $t_i>0$ for all $i$. Then, note that \[t_{i+1}-t_i=(s_{s_{i+1}+1}-s_{s_{i+1}})-(s_{s_i+1}-s_{s_i})=e-d\]so $t_i$ is an arithmetic sequence. Since it is bounded on both sides, it is constant, which implies $d=e$. Note that \[d\ge s_{s_{i+1}}-s_{s_i}\ge \sum_{j=s_i}^{s_{i+1}-1}{s_{j+1}-s_j}\ge\sum_{j=s_i}^{s_{i+1}-1}{1}\ge s_{i+1}-s_i\]so $s_{i+1}-s_i$ is bounded. Let it achieve minimum value at $s_{a+1}-s_a=m$ for all $a\in A$ and maximum value at $s_{b+1}-s_b=M$ for all $b\in B$. Then, \[m(s_{s_{a+1}}-s_{s_a})=md=d(s_{a+1}-s_a)=s_{s_{s_{a+1}}}-s_{s_{s_a}}=\sum_{j=s_{s_{a}}}^{s_{s_{a+1}}-1}{s_{j+1}-s_j}\]but the expression $s_{j+1}-s_j$ is at least $m$, so it must be equal to $m$ for all $j\in[s_{s_{a}},s_{s_{a+1}})$. Similarly, $s_{j+1}-s_j=M$ for all $j\in[s_{s_{b}},s_{s_{b+1}})$. However, $m=s_{s_a+1}-s_{s_a}=t_a=t_b=s_{s_b+1}-s_{s_b}=M$ so we're done.

Phrasing everything as a function $f: \mathbb Z_{>0} \to \mathbb Z_{>0}$ we have that we are given $f(f(n+1))-f(f(n))=r_1$ and $f(f(n+1)+1)-f(f(n)+1)=r_2$ for all positive integers $n$, and that $f$ is strictly increasing. $$f(f(1)+1)+nr_1>f(f(1))+nr_1=f(f(n+1)) \ge f(f(n)+1)=f(f(1)+1)+(n-1)r_2 \implies r_1>\frac{(n-1)r_2}{n} \overset{n \to \infty}{\implies} r_1 \ge r_2$$$$f(f(1)+1)-f(f(1))=f(f(n)+1)-f(f(n))+(n-1)(r_1-r_2)>(n-1)(r_1-r_2) \overset{n \to \infty}{\implies} r_1=r_2$$Now clearly $f(i+1)-f(i)$ is bounded above and below since $f$ is strictly increasing and if it was unbounded above then notice that now that we have $f(f(n+1)+1)-f(f(n)+1)=r_1=f(f(n+1))-f(f(n))$ then the gap has to be finite otherwise we would get a size contradiction. Now note that such equations also give $f(f(n+1)+1)-f(f(n+1))=f(f(n)+1)-f(f(n))=c$ constant. Let $m \le f(n+1)-f(n) \le M$ for all positive integers $n$ where $m,M$ are minimun and maximun respectively, then we set $f(v+1)=f(v)+m$ and $f(u+1)=f(u)+M$, now note that $Mm \ge f(f(v)+m)-f(f(v))=r_1=f(f(u)+M)-f(f(u)) \ge Mm$ so $r_1=Mm$ but then the other inequalities must be equalities such as $f(f(v)+\ell)-f(f(v)+\ell-1)=M$ for all $m \ge \ell \ge 1$ and $f(f(u)+\alpha)-f(f(u)+\alpha-1)=m$ for all $M \ge \alpha \ge 1$ which means that $M=c=m$ by setting $\ell=\alpha=1$ therefore $f(n+1)-f(n)$ is constant for all positive integers $n$ thus we are done .