The sequence $a_1,a_2,\dots$ of integers satisfies the following conditions:

(i) $1\le a_j\le 2015$ for all $j\ge 1$;

(ii) $k+a_k\ne \ell +a_{\ell }$ for all $1\le k<\ell$.

Prove that there exist two positive integers $b$ and $N$ such that

for all integers $n\ge N$.

Step 1 (Reformulation): Condition (ii) says the map $j\mapsto j+a_j$ is injective. Since $a_j\in \{1,\dots ,2015\}$, the values $j+a_j$ for $j=1,2,\dots$ form an infinite subset of $\{2,3,4,\dots \}$ with no repeats. Consider the "carrier lines" $L_c=\{j:j+a_j=c\}$; each has at most one element by (ii). So for each $c\ge 2$, at most one index $j$ satisfies $j+a_j=c$.

Step 2 (Density argument): Among the integers $c\in \{n+1,n+2,\dots ,n+2015\}$, the values $j+a_j$ with $j\le n$ cover at most $n$ of them (and exactly those with $j\le n$ and $a_j=c-j\in [1,2015]$, i.e., $c-2015\le j\le c-1$). For large $n$, among $c\in [n+1,n+2015]$, most are "used" by $j$ close to $n$.

Step 3 (Key insight): The function $a_j$ must eventually settle into a near-constant pattern. Specifically, for large $j$, $a_j$ takes each value in $\{1,\dots ,2015\}$ roughly equally often among consecutive blocks (by the pigeonhole principle applied to the injective condition). The "average" value of $a_j$ over long blocks approaches some integer $b$.

Step 4 (Bounding partial sums): Choose $b$ as the value most frequently taken by $a_j$ (or more precisely, the value that minimizes the drift). The injectivity of $j+a_j$ ensures that the partial sums ${\sum }_{j=1}^n(a_j-b)$ cannot drift by more than the range of $a_j$ squared, since each "carrier" $c$ is used at most once. The maximum deviation is bounded by $2015^2$.

$■$