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 3 of 5: Pin the maximum increment at the doubly-composed index

Previous step Next step

d_a=M \implies d_{s(s(a))}=\dots=d_{s(s(a+1))-1}=M \implies M=B-A

Detailed analysis

Pick $a$ with $d_a=M$ . Applying $s(s(m))=Dm+A$ at $m=s(a)$ and $m=s(a+1)$ gives $s(s(s(a+1)))-s(s(s(a)))=D\big(s(a+1)-s(a)\big)=DM$ . But this same quantity telescopes as the sum of the $D$ consecutive differences $d_{s(s(a))}+\dots+d_{s(s(a+1))-1}$ (since $s(s(a+1))-s(s(a))=D$ ). Each of these $D$ terms is $\le M$ by definition of $M$ , so their sum is $\le DM$ , with equality just shown to hold; equality forces every one of the $D$ terms to equal $M$ exactly. In particular $d_{s(s(a))}=M$ . But Step 2 (with $n=s(a)$ ) says $d_{s(s(a))}=B-A$ . Hence $M=B-A$ .