Solution to puzzle 52: Floor function sum

We must prove (1): [x] + [x + 1/n] + ... + [x + (n−1)/n] = [nx], where x is a real number and n is a positive integer.

The result is trivial for n = 1.

For n > 1, write x in number base n: x = [x] + 0.d₁d₂d₃..., where d₁... are digits between 0 and n − 1.
If we restrict ourselves to writing terminating rational numbers with trailing zeroes, rather than with recurring (n − 1)s, then each real number has a unique representation in base n. (For example, we agree to write decimal −2.3 as −3 + 0.7000..., rather than as −3 + 0.6999...; though the two forms are numerically equal.)

Then, on the right-hand side of (1): nx = (n[x] + d₁) + 0.d₂d₃... .
Hence [nx] = n[x] + d₁.

On the left-hand side of (1):
[x] + [0.rd₂d₃...] = [x], for d₁ r n−1, and
[x] + 1 + [0.sd₂d₃...] = [x] + 1, for 0 s d₁−1. (No terms if d₁ = 0.)

There are n terms, d₁ of which equal [x] + 1, so the sum is n[x] + d₁.

Therefore [x] + [x + 1/n] + ... + [x + (n−1)/n] = [nx].

(Note: The result can be established without working in base n, but doing so provides a useful shorthand.)

Solution to puzzle 52: Floor function sum

Further reading