Summation over k of Ceiling of mk+x over n
Jump to navigation
Jump to search
Theorem
Let $m, n \in \Z$ such that $n > 0$.
Let $x \in \R$.
Then:
- $\ds \sum_{0 \mathop \le k \mathop < n} \ceiling {\dfrac {m k + x} n} = \dfrac {\paren {m + 1} \paren {n - 1} } 2 - \dfrac {d - 1} 2 + d \ceiling {\dfrac x d}$
where:
- $\ceiling x$ denotes the ceiling of $x$
- $d$ is the greatest common divisor of $m$ and $n$.
Proof
\(\ds \sum_{0 \mathop \le k \mathop < n} \ceiling {\dfrac {m k + x} n}\) | \(=\) | \(\ds \sum_{0 \mathop \le k \mathop < n} \paren {-\floor {-\dfrac {m k + x} n} }\) | Floor of Negative equals Negative of Ceiling | |||||||||||
\(\ds \) | \(=\) | \(\ds -\sum_{0 \mathop \le k \mathop < n} \floor {\dfrac {-m k - x} n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds -\paren {\dfrac {\paren {\paren {-m} - 1} \paren {n - 1} } 2 + \dfrac {d - 1} 2 + d \floor {\dfrac {\paren {-x} } d} }\) | Summation over $k$ of $\floor {\dfrac {m k + x} n}$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\paren {m + 1} \paren {n - 1} } 2 - \dfrac {d - 1} 2 - d \floor {-\dfrac x d}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\paren {m + 1} \paren {n - 1} } 2 - \dfrac {d - 1} 2 + d \ceiling {\dfrac x d}\) | Floor of Negative equals Negative of Ceiling |
$\blacksquare$
Sources
- 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 $37$: Answers to Exercises