Summation over k of Floor 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} \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\)



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