Prove this Floor function indentity $\sum_{k=0}^{n-1} \bigl\lfloor \frac{ak+b}{c} \bigr\rfloor$

Question

Assume $a,b,c$ be positive integers. Show that:

$$\sum_{k=0}^{n-1} \left\lfloor \frac{ak+b}{c} \right\rfloor = \sum_{k=0}^{\left\lfloor \dfrac{an+b}{c}\right\rfloor} \left\lfloor\dfrac{ck+(an+b)\pmod {c}}{a}\right\rfloor$$

My approach is the following:

let $an+b=cl+r,0\le r<c$, then we have $\left\lfloor \dfrac{an+b}{c} \right\rfloor=l$, For the right hand $$\sum_{k=0}^{\left\lfloor \dfrac{an+b}{c}\right\rfloor} \left\lfloor\dfrac{ck+(an+b)\pmod {c}}{a}\right\rfloor=\sum_{k=0}^{l}\left\lfloor\dfrac{k+r}{a}\right\rfloor$$

Well and now I'm stuck and don't know how to proceed.

Answer 1

Here is a way to compute LHS. Consider line $L$ in the plane defined by $y = \frac{ax+b}{c}$. Clearly, LHS is counting the lattice points in $[0,n)\times (0,\infty]$ on/under the line. Call the set of such lattice points $A$.

Alternatively, one may count lattice points in $A$ "horizontally". Specifically, for each $y\in \{1, \ldots, Y\}$, where $Y:=\lfloor(an+b)/c\rfloor$, the largest possible $y$-coordinate of points in $A$, the size of $A_y := A\cap [0,n)\times \{y\}$ is equal to

1. $n$, if $y \leq a/c$.
2. $\lfloor\frac{an+b-cy}{a}\rfloor$,if $y > a/c$.

Therefore, one may change RHS to $$n\lfloor a/c \rfloor + \sum_{k=\lfloor a/c\rfloor+1}^{\lfloor(an+b)/c\rfloor}\lfloor\frac{an+b-ck}{a}\rfloor.$$