Subtract Half is Replicative Function
Jump to navigation
Jump to search
Theorem
Let $f: \R \to \R$ be the real function defined as:
- $\forall x \in \R: \map f x = x - \dfrac 1 2$
Then $f$ is a replicative function.
Proof
\(\ds \sum_{k \mathop = 0}^{n - 1} \map f {x + \frac k n}\) | \(=\) | \(\ds \sum_{k \mathop = 0}^{n - 1} \paren {x - \frac 1 2 + \frac k n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds n x - \frac n 2 + \frac 1 n \sum_{k \mathop = 0}^{n - 1} k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds n x - \frac n 2 + \frac 1 n \frac {n \paren {n - 1} } 2\) | Closed Form for Triangular Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds n x - \frac n 2 + \frac n 2 - \frac 1 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds n x - \frac 1 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \map f {n x}\) |
Hence the result by definition of replicative function.
$\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 $39 \ \text{a)}$