Problem 6

The sequence

a_1,a_2,\dots

of integers satisfies the conditions: (i)

1\le a_j\le 2015

for all

j\ge1

; (ii)

k+a_k\ne \ell+a_\ell

for all

1\le k<\ell

. Prove that there exist two positive integers

b

and

N

for which

\left|\sum_{j=m+1}^{n}(a_j-b)\right|\le 1007^2

for all integers

m

and

n

such that

n>m\ge N

Step 4 of 6: Splitting the target sum by chain

Previous step Next step

In plain words

Subtracting $b$ from each term of the sum exactly compensates for adding one overshoot term per chain.

\sum_{j=m+1}^{n}(a_j-b)=\sum_{\text{chain }c}\Big[\big(\min\{x>n:x\in c\}-n\big)-\big(\min\{x>m:x\in c\}-m\big)\Big]

Detailed analysis

Summing the previous step's telescoping identity over all $b$ chains and comparing with $\sum_{j=m+1}^n a_j=\sum_{j=m+1}^n\big(f(j)-j\big)$ , one finds that $\sum_{j=m+1}^n(a_j-b)$ equals exactly the sum over the $b$ chains $c$ of $\big(\min\{x>n:x\in c\}-n\big)-\big(\min\{x>m:x\in c\}-m\big)$ : each chain contributes one overshoot-past-the-boundary term at $n$ and one at $m$ , and there are exactly $b$ chains, matching the $-b$ correction applied to each of the $n-m$ indices.