Here’s something I ran across in Volume 2 of Donald Knuth’s The Art of Computer Programming.
Knuth defines the sawtooth function by
((x)) = x – (⌊x⌋ + ⌈x⌉)/2.
Here’s a plot.
This is an interesting way to write the sawtooth function, one that could make it easier to prove things about, such as the following theorem. For positive integers n, we have
It’s not at all obvious, at least to me, that this should be true.
Knuth does not give a proof but leaves the proof to Exercise 2 in Section 3.3.3. I suppose you could prove it by slugging it out with floor and ceiling identities, but I looked at the solutions to see whether Knuth has a more elegant proof.
The solution for Exercise 2 says to see exercises 38 and 39 in Volume 1, section 1.2.4. These exercises break the problem of proving the theorem above into smaller parts. They also generalize the problem, defining a function f to be replicative if it satisfies the equation
The theorem above says that the sawtooth function is replicative. Other examples of replicative functions include the floor function and the function that takes x to x – ½.
3 thoughts on “Sawtooth and replicative functions”
This replicative identity comes from the corresponding identity for Bernoulli polynomials (scaled by a suitable factor) as the saawtooth function is more or less the first Bernoulli polynomial: https://en.wikipedia.org/wiki/Bernoulli_polynomials#Multiplication_theorems
An analogous identity, with the sum replaced by a product holds for the Gamma function as well (scaled by a factor as well): https://en.wikipedia.org/wiki/Gamma_function#Pi_function
Both identities (and presumably many more!) boil down to a identity coming from the geometric series and the exponential function, see this paper from Granville & Zun on p. 123 (7th page in the PDF file): https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-172/issue-1/Values-of-Bernoulli-polynomials/pjm/1102366187.full
(They refer to Lerch “Zur Theorie des Fermatschen Quotienten” in Math. Ann. 60 (1905), 471-490, but I couldn’t find the identity there ad hoc.)
I think this is also know as Hermite’s identity
Quite obvious but not seen in TAOCP:
For replicative f always f(1/2) = 0.
There is some text on replicative functions in the ProofWiki,
BUT they did not even get the definition right:
ForAll integers n >= 0: f(nx) = …
instead of correctly n > 0.