Summation over k of Floor 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} \floor {\dfrac {m k + x} n} = \dfrac {\paren {m - 1} \paren {n - 1} } 2 + \dfrac {d - 1} 2 + d \floor {\dfrac x d}$
where:
- $\floor x$ denotes the floor of $x$
- $d$ is the greatest common divisor of $m$ and $n$.
Proof
By definition of modulo 1:
- $\ds \sum_{0 \mathop \le k \mathop < n} \floor {\dfrac {m k + x} n} = \sum_{0 \mathop \le k \mathop < n} \dfrac {m k + x} n - \sum_{0 \mathop \le k \mathop < n} \fractpart {\dfrac {m k + x} n}$
where $\fractpart y$ in this context denotes the fractional part of $y$.
First we have:
\(\ds \sum_{0 \mathop \le k \mathop < n} \dfrac {m k + x} n\) | \(=\) | \(\ds \frac m n \sum_{0 \mathop \le k \mathop < n} k + \sum_{0 \mathop \le k \mathop < n} \dfrac x n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac m n \frac {n \paren {n - 1} } 2 + n \dfrac x n\) | Closed Form for Triangular Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {m \paren {n - 1} } 2 + x\) |
Let $S$ be defined as:
- $\ds S := \sum_{0 \mathop \le k \mathop < n} \fractpart {\dfrac {m k + x} n}$
Thus:
- $(1): \quad \ds \sum_{0 \mathop \le k \mathop < n} \floor {\dfrac {m k + x} n} = \dfrac {m \paren {n - 1} } 2 + x - S$
Let $d = \gcd \set {m, n}$.
Let:
\(\ds t\) | \(=\) | \(\ds \frac n d\) | ||||||||||||
\(\ds u\) | \(=\) | \(\ds \frac m d\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \frac m n\) | \(=\) | \(\ds \frac u t\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds m t\) | \(=\) | \(\ds u n\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds u\) | \(=\) | \(\ds \frac {m t} n\) |
We have that:
\(\ds \fractpart {\dfrac {m k + x} n}\) | \(=\) | \(\ds \fractpart {\dfrac {m k + x} n + u}\) | Definition of Fractional Part: $u$ is an integer | |||||||||||
\(\ds \) | \(=\) | \(\ds \fractpart {\dfrac {m k + x} n + \frac {m t} n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \fractpart {\dfrac {m \paren {k + t} + x} n}\) |
Thus $S$ consists of $d$ copies of the same summation:
\(\ds S\) | \(=\) | \(\ds \sum_{0 \mathop \le k \mathop < n} \fractpart {\dfrac {m k + x} n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds d \sum_{0 \mathop \le k \mathop < t} \fractpart {\dfrac {m k + x} n}\) |
and so:
\(\ds \sum_{0 \mathop \le k \mathop < t} \fractpart {\dfrac {m k + x} n}\) | \(=\) | \(\ds \sum_{0 \mathop \le k \mathop < t} \fractpart {\dfrac x n + \dfrac {u k} t}\) | substituting $\dfrac u t$ for $\dfrac m n$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{0 \mathop \le k \mathop < t} \fractpart {\dfrac {x \bmod d} n + \dfrac k t}\) | as $t \perp u$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{0 \mathop \le k \mathop < t} \dfrac {x \bmod d} n + \dfrac k t\) | as $\dfrac {x \bmod d} n < \dfrac 1 t$ | |||||||||||
\(\ds \) | \(=\) | \(\ds t \dfrac {x \bmod d} n + \frac 1 t \sum_{0 \mathop \le k \mathop < t} k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {t \paren {x \bmod d} } n + \frac 1 t \frac {t \paren {t - 1} } 2\) | Closed Form for Triangular Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {t \paren {x \bmod d} } n + \frac {t - 1} 2\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds S\) | \(=\) | \(\ds d \paren {\dfrac {t \paren {x \bmod d} } n + \frac {t - 1} 2}\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {n \paren {x \bmod d} } n + \frac {n - d} 2\) | as $n = d t$ | |||||||||||
\(\ds \) | \(=\) | \(\ds x \bmod d + \frac {n - d} 2\) |
This article, or a section of it, needs explaining. In particular: Greater detail needed as to why $\ds \sum_{0 \mathop \le k \mathop < t} \fractpart {\dfrac x n + \dfrac {u k} t} = \sum_{0 \mathop \le k \mathop < t} \fractpart {\dfrac {x \bmod d} n + \dfrac k t}$ You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code. |
Thus:
\(\ds \sum_{0 \mathop \le k \mathop < n} \floor {\dfrac {m k + x} n}\) | \(=\) | \(\ds \frac {m \paren {n - 1} } 2 + x - S\) | from $(1)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {m \paren {n - 1} } 2 + x - d \paren {\dfrac {t \paren {x \bmod d} } n + \frac {t - 1} 2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {m \paren {n - 1} } 2 + x - x \bmod d - \frac {n - d} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {m \paren {n - 1} } 2 + x - x + d \floor {\frac x d} - \frac {n - 1} 2 + \frac {d - 1} 2\) | Definition of Modulo Operation and algebra | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {m - 1} \paren {n - 1} } 2 + \frac {d - 1} 2 + d \floor {\frac x d}\) | simplification |
$\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$