The number of intersecting $k$-arithmetic progressions below $n$ is capped by $nk$

Question

I found this as an exercise in the context of capping Van der Waerden numbers:

For a given arithmetic progression $S \subseteq [n] = \{1,...,n\}$ with $|S| = k$ there are at most $nk$ other such progressions $T$ with $S \cap T \neq \emptyset$.

I came really close with this technique: Given $S = \{a_1 + i d_1: 0 \le i \le k-1\}$ we pick an intersecting $T = \{a_2 + i d_2: 0 \le i \le k-1\}$ by first picking $i,j$ (with $k^2$ possibilities) as the indices of their first intersection point $$x := a_1 + i d_1 = a_2 + j d_2$$ Then we pick $d_2$ from which $a_2$ and thus $T$ are fixed, so we want $\frac{n}{k}$ possibilities here. The first and last element of $T$ have to be in $[n]$, so $$x-jd_2 \ge 1$$ $$x+(n-1-k)d_2 \le n$$ from which we get $$1 \le d_2 \le \frac{x-1}{j}$$ $$1 \le d_2 \le \frac{x-n}{n-1-k}$$ At first I forgot the $-1$ in the second inequality, which easily leads to at least one of them yielding $\le \frac{n}{k}$ possibilities for $d_2$. With the $-1$ though I only get really close to $\frac{n}{k}$ but can't get to it...

Answer 1

The number of such progressions does not exceed even $(n-2)k$. It suffices to prove that for each fixed $t\in \{1,\ldots,n\}$ the number of progressions containing $t$ is at most $n-1$ (subtract 1 for our progression $S$ and sum up over $t\in S$).

The number of progressions for which $t$ is the last term does not exceed $(t-1)/(k-1)$. The number of progressions for which $t$ is the first term does not exceed $(n-t)/(k-1)$. For each $j=2,\ldots,k-1$ the number of progressions for which $t$ is the $j$-th largest term does not exceed $(n-1)/(k-1)$, since the difference of progression does not exceed $(n-1)/(k-1)$, and the progression is uniquely determined by the difference and $j$-th term. Totally at most $$\frac{(t-1)+(n-t)+(k-2)(n-1)}{k-1}=n-1$$ progressions.