N2

lemma 1: alle $a_i$ zijn verschillend.
bewijs: Als $a_i=a_j$ voor indices $i>j$, dan moet gelden dat $a_i\not\equiv a_j \pmod{i}$, een directe contradictie.

lemma 2: voor alle $n>i>0$ geldt $\mid a_n-a_i\mid < n$
bewijs: Er geldt dat $a_n\equiv a_i\pmod{|a_n-a_i|}$ en dus geldt wegens de modulo-eigenschap $|a_n-a_i| < max(n,i)=n$ omdat anders $a_n$ en $a_i$ beide dezelfde rest hebben bij deling door $|a_n-a_i|$.

Laat wlog $a_1\geq 0$ en zij $k$ minimaal zodat $a_{k+1} < 0$.

lemma 3: $\{a_1,a_2,\dots, a_k\}=\{0,1,\dots, k-1\}$
bewijs: wegens de definitie van $k$ en lemma $1$ volstaat het te bewijzen dat $a_i < k$ voor alle $1\le i \le k$. lemma 2 zegt dat $|a_i-a_{k+1}| < k$. Omdat $a_{k+1}$ strikt negatief is, $a_i < k+a_{k+1} < k$.

lemma 4: de verzameling $\{a_1,a_2,\dots, a_n\}$ voor $n\ge k$ is een verzameling van $n$ opeenvolgende gehele getallen.
bewijs: lemma 3 geeft de inductiebasis. Neem nu aan dat het klopt voor een zeker $n\ge k$. laat $a_m=min_{i=1,\dots, n}(a_i)$ en $a_M=max_{i=1,\dots, n}(a_i)$
Omdat $|a_{n+1}-a_m|\le n$ en $|a_{n+1}-a_M|\le n$ (lemma 2) geldt dat $a_M-n\le a_{n+1}\le n+a_m$. Er zijn dus $a_m+n-(a_M-n)+1=n+2$ waarden mogelijk voor $a_{n+1}$ (hier gebruikten we de inductiehypothese). Houden we rekening met lemma $1$ en dat $a_M-n\le a_i\le a_m+n $ voor alle $1\le i \le n$, zien we dat de enige mogelijke waarden voor $a_{n+1}$ precies $a_M+1$ en $a_m-1$ zijn, zoals gevraagd.

Er geldt bovendien precies $a_{n+1}=a_m-1$ als $a_{n+1}$ negatief is en omgekeerd. Omdat er oneindig veel $a_i$ negatief en positief zijn, zijn we klaar wegens lemma 4.