Problem 3

Suppose that

s_1, s_2, s_3, \dots

is a strictly increasing sequence of positive integers such that the subsequences

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.

Step 1 of 5: Write both progressions with the same common difference D

Previous step Next step

In plain words

Sandwiching s(s(n)) between s(s(n)+1) and s(s(n+1)) forces the two given arithmetic progressions to share a common difference.

s(s(n))=Dn+A,\quad s(s(n)+1)=Dn+B\quad (A<B\le A+D)

Detailed analysis

Write $s(n)$ for $s_n$ . Since $\left(s(s(n))\right)_{n\ge1}$ is an arithmetic progression, $s(s(n))=Dn+A$ for constants $D,A$ ; since $\left(s(s(n)+1)\right)_{n\ge1}$ is one too, $s(s(n)+1)=D'n+B$ for constants $D',B$ . Because $s$ is strictly increasing and $s(n)<s(n)+1\le s(n+1)$ , applying $s$ gives $s(s(n))<s(s(n)+1)\le s(s(n+1))$ , i.e. $Dn+A<D'n+B\le D(n+1)+A$ for every $n\ge1$ . Since this must hold for all $n$ , the coefficients of $n$ must agree: $D=D'$ . Then the inequality reduces to $A<B\le A+D$ .