Summation over k of Floor of x plus k over y

Theorem

Let $x, y \in \R$ such that $y > 0$.

Then:

$\displaystyle \sum_{0 \mathop \le k \mathop < y} \left \lfloor{x + \dfrac k y}\right \rfloor = \left \lfloor{x y + \left \lfloor{x + 1}\right \rfloor \left({\left \lceil{y}\right \rceil - y}\right)}\right \rfloor$

Proof

When $x$ increases by $1$, both sides increase by $\left \lceil{y}\right \rceil$.

So we can assume $0 \le x < 1$.

When $x = 0$, both sides are equal to $0$.

When $x$ increases past $1 - \dfrac k y$ for $0 \le k < y$, both sides increase by $1$.

Hence the result.

$\blacksquare$

Historical Note

The summation over $k$ of $\floor{x + \dfrac k y}$ is attributed to E. Busche, who published this result in $1909$.

Little biographical information can be found about him.

Sources

• 1909: E. Busche: Zur Theorie die Funktion $\left[{x}\right]$ (J. reine angew. Math. Vol. 136: pp. 39 – 57)

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $38$