Lemma: Sums of Floors

For any real number $\alpha\in\mathbb R$ and any two integers $x,y\in\mathbb Z$ with $y\neq 0,$ the following closed formula for the sum of floor function holds: $$\sum_{k=0}^{y-1}\left\lfloor\frac{xk+\alpha}m\right\rfloor=d\left\lfloor\frac{\alpha}d\right\rfloor +\frac{y-1}{2}x+\frac{d-y}{2},$$ where $d=\gcd(x,y)$ is the greatest common divisor of $x$ and $y.$

Proofs: 1


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Graham L. Ronald, Knuth E. Donald, Patashnik Oren: "Concrete Mathematics", Addison-Wesley, 1994, 2nd Edition