Summation over k of Ceiling of mk+x over n

From ProofWiki
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