Closed form for a floor sum

Question

I want to compute

$$\sum_{i=a}^b \left\lfloor \frac{i}{k} \right\rfloor$$

Where $k < b < \infty$, and $a > 0$. I don't know where to begin (or if there's a closed form, for that matter), so any hints would be appreciated!

Answer 1

Start with what we know: $\lfloor\frac{i}{k}\rfloor$ is the same as the computer science integer divide. That is, it gives us the whole part of long division and drops the remainder.

Next, we know that every whole number will appear at most $k$ times, since that is how many fractions exist between $0$ and $1$ and have denominator $k$ (excluding one endpoint).

Next, $\lfloor\frac{b}{k}\rfloor-\lfloor\frac{a}{k}\rfloor$ tells us how many whole numbers we will see at least once each.

What you end up with is $$\left(k\sum\limits_{i=\left\lceil\frac{a}{k}\right\rceil}^{\left\lfloor\frac{b}{k}\right\rfloor}i\right)+\left(r(b,k)\left\lfloor\frac{b}{k}\right\rfloor\right)+\left((k-r(a,k))\left\lfloor\frac{a}{k}\right\rfloor\right)$$

The first term in this accounts for all the whole numbers that appear exactly $k$ times. The second term accounts for the highest integers that appear, and similarly for the final term with the lowest integers. The function $r(x,y)$ here represents the remainder in the division $x/y$.

The first term can be simplified using the fact that $$\sum\limits_{i=1}^ni=\frac{n(n+1)}{2}$$ so that the result is $$k\left(\frac{\left\lfloor\frac{b}{k}\right\rfloor\left(\left\lfloor\frac{b}{k}\right\rfloor+1\right)-\left\lceil\frac{a}{k}\right\rceil\left(\left\lceil\frac{a}{k}\right\rceil-1\right)}{2}\right)+\left(r(b,k)\left\lfloor\frac{b}{k}\right\rfloor\right)+\left((k-r(a,k))\left\lfloor\frac{a}{k}\right\rfloor\right)$$

With any luck, this makes sense and isn't completely stupid.