Problem: Suppose that $s_1,s_2,s_3, \dotsc$ is a strictly increasing sequence of
positive integers such that the sub-sequences
$s_{s_1}$, $s_{s_2}$, $s_{s_3}$, \dots
and $s_{s_1 + 1}$, $s_{s_2 + 1}$, $s_{s_3 + 1}$, \dots
are both arithmetic progressions.
Prove that the sequence $s_1$, $s_2$, $s_3$, \dots\ is itself an arithmetic progression.

Solution: We present two solutions.

\paragraph{First solution (Alex Zhai).}
Let $s(n) \coloneq s_n$ and write
\begin{align*}
  s(s(n)) &= Dn + A \\
  s(s(n)+1) &= D'n + B.
\end{align*}
In light of the bounds $s(s(n)) \le s(s(n)+1) \le s(s(n+1))$
we right away recover $D = D'$ and $A \le B$.

Let $d_n = s(n+1)-s(n)$.
Note that $\sup d_n < \infty$ since $d_n$ is bounded above by $A$.

Then we let
\[ m \coloneq \min d_n, \qquad M \coloneq \max d_n. \]
Now suppose $a$ achieves the maximum, meaning $s(a+1)-s(a) = M$.
Then
\begin{align*}
  \underbrace{d_{s(s(a))} + \dots + d_{s(s(a+1))-1}}_{D \text{ terms}}
  &= \boxed{s(s(s(a+1))) - s(s(s(a)))} \\
  &= (D \cdot s(a+1) + A) - (D \cdot s(a) + A) = DM.
\end{align*}
Now $M$ was maximal hence $M = d_{s(s(a))} = \dots = d_{s(s(a+1))-1}$.
But $d_{s(s(a))} = B-A$ is a constant.
Hence $M = B-A$.
In the same way $m = B-A$ as desired.

\paragraph{Second solution.}
We retain the notation $D$, $A$, $B$ above,
as well as $m = \min_n s(n+1)-s(n) \ge B-A$.
We do the involution trick first as:
\[ D = \boxed{s(s(s(n)+1)) - s(s(s(n)))} = s(Dn+B) - s(Dn+A) \]
and hence we recover $D \ge m(B-A)$.

The edge case $D = B-A$ is easy since then $m=1$
and $D = s(Dn+B)-s(Dn+A)$ forces $s$ to be a constant shift.
So henceforth assume $D > B-A$.

The idea is that right now the $B$ terms are ``too big'',
so we want to use the involution trick in a way that makes as many
``$A$ minus $B$'' shape expressions as possible.
This motivates considering $s(s(s(n+1))) - s(s(s(n)+1)+1) > 0$,
since the first expression will have all $A$'s
and the second expression will have all $B$'s.
Calculation gives:
\begin{align*}
  s(D(n+1)+A) - s(Dn+B+1)
  &= \boxed{s(s(s(n+1))) - s(s(s(n)+1)+1)} \\
  &= (Ds(n+1) + A) - (D(s(n)+1) + B) \\
  &= D\left( s(n+1)-s(n) \right) + A-B-D.
\end{align*}
Then by picking $n$ achieving the minimum $m$,
\[ \underbrace{m(D+A-B-1)}_{>0} \le s(s(s(n+1))) - s(s(s(n)+1)+1) \le Dm + A-B-D \]
which becomes
\[ \left( D-m(B-A) \right) + \left( (B-A)-m \right) \le 0. \]
Since both of these quantities were supposed to be nonnegative,
we conclude $m = B-A$ and $D = m^2$.
Now the estimate $D = s(Dn+B) - s(Dn+A) \ge m(B-A)$ is actually sharp,
so it follows that $s(n)$ is arithmetic.