How many $k$-element arithmetic progressions exist among the numbers $1,2,...,n$?

Question

How many possible arithmetic progressions of length $k$ exist where all elements are in the set $\left\{1,2,\dots,n\right\}$? We can assume the step of the progression to be a natural number.

Example: For $k=3$, $n=5$ we have four progressions: $(1,2,3), (2,3,4), (3,4,5), (1,3,5)$.

---

Additional (related) question: For a fixed $k$-element progression $A = (\alpha_1,\alpha_2, \dots, \alpha_k)$, what is the highest possible number of different $k$-element progressions that contain the element $\alpha_i$, where $1\leq i \leq k$?

Example: For $k=3$, $n=5$ we can see that the element $3$ appears in every progression, so the highest possible number of progressions is $4$.

Answer 1

Let $j$ be the least element of one of these progressions. Then $1\le j\le n-k+1$. If $d$ is the difference of the progression, then $j+(k-1)d\le n$, so $$1\le d\le \frac{n-j}{k-1}$$ Since $d$ must be an integer, there are $$\left\lfloor\frac{n-j}{k-1}\right\rfloor$$ possible values for $d$. This makes the same number of arithmetic progressions that begin with $j$.

So the total number of progressions is $$S=\sum_{j=1}^{n-k+1}\left\lfloor\frac{n-j}{k-1}\right\rfloor=\sum_{j=k-1}^{n-1}\left\lfloor\frac{j}{k-1}\right\rfloor=\sum_{j=1}^{n-1}\left\lfloor\frac{j}{k-1}\right\rfloor$$

If the Euclidean division $(n-1)/(k-1)$ gives $n-1=q(k-1)+r$ then this sum consists on some zeros, $k-1$ times $1,\ldots,k-1$ times $q-1$, and finally $r+1$ times $q$. Note that if $r=0$ then the term $q$ occurs only once at the very end.

Thus, $$S=\frac{(k-1)q(q-1)}2+q(r+1)$$

Answer 2

Alternatively you might want an explicit formula in terms of $n$ and $k$, and this approach counts the AP's slightly differently.

For a fixed $n$ and $k$ there are $\lfloor \frac{n-1}{k-1} \rfloor$ possible values that the arithmetic difference $d$ can take, as we have at least one sequence for each $d>0$ satisfying $(k-1)d + 1 \leq n$. For each such $d$ there are $n-(k-1)d$ arithmetic progressions in $[n]$. Hence we have

\begin{align} \sum_{d=1}^{\lfloor \frac{n-1}{k-1} \rfloor} n - (k-1)d &= n \lfloor \frac{n-1}{k-1} \rfloor + \frac{k-1}{2}\lfloor \frac{n-1}{k-1} \rfloor \big(\lfloor \frac{n-1}{k-1} \rfloor + 1\big) \\ &= \lfloor \frac{n-1}{k-1} \rfloor\big(n - \frac{k-1}{2}(\lfloor \frac{n-1}{k-1} \rfloor + 1) \big) \end{align}

For the additional question, see this mathoverflow post which gives an upper bound but with similar logic could be adapted to give an explicit answer.

Edit: the general reason I prefer this method is that more often than not having floor functions in the summand can make closed form solutions difficult to derive, but having a floor function in the limits of the sum are usually quite easy to work with.