Summation over k of Floor of x plus k over y
Jump to navigation
Jump to search
Theorem
Let $x, y \in \R$ such that $y > 0$.
Then:
- $\ds \sum_{0 \mathop \le k \mathop < y} \floor {x + \dfrac k y} = \floor {x y + \floor {x + 1} \paren {\ceiling y - y} }$
Proof
When $x$ increases by $1$, both sides increase by $\ceiling y$.
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 Edmund Busche, who published this result in $1909$.
Sources
- 1909: E. Busche: Zur Theorie die Funktion $\sqbrk x$ (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$