Demostrar la identidad de la función del suelo $\sum_{k=0}^{n-1} \bigl\lfloor \frac{ak+b}{c} \bigr\rfloor$

Question

Supongamos que $a,b,c$ sean enteros positivos. Demostrar que:

$$\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$$

Mi enfoque es el siguiente:

dejar $an+b=cl+r,0\le r<c$ entonces tenemos $\left\lfloor \dfrac{an+b}{c} \right\rfloor=l$ , Para la mano derecha $$\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$$

Bueno y ahora estoy atascado y no sé cómo proceder.

Answer 1

Esta es una forma de calcular el LHS. Considere la línea $L$ en el plano definido por $y = \frac{ax+b}{c}$ . Claramente, LHS está contando los puntos de la red en $[0,n)\times (0,\infty]$ en/bajo la línea. Llamamos al conjunto de tales puntos de la red $A$ .

Como alternativa, se pueden contar los puntos de la red en $A$ "horizontalmente". En concreto, para cada $y\in \{1, \ldots, Y\}$ , donde $Y:=\lfloor(an+b)/c\rfloor$ el más grande posible $y$ -coordenadas de puntos en $A$ El tamaño de $A_y := A\cap [0,n)\times \{y\}$ es igual a

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

Por lo tanto, se puede cambiar la RHS por $$n\lfloor a/c \rfloor + \sum_{k=\lfloor a/c\rfloor+1}^{\lfloor(an+b)/c\rfloor}\lfloor\frac{an+b-ck}{a}\rfloor.$$