Skip to main content.

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.d1d2d3..., where d1... 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] + d1) + 0.d2d3... .
Hence [nx] = n[x] + d1.

On the left-hand side of (1):
[x] + [0.rd2d3...] = [x], for d1 less than or equal to r less than or equal to n−1, and
[x] + 1 + [0.sd2d3...] = [x] + 1, for 0 less than or equal to s less than or equal to d1−1.  (No terms if d1 = 0.)

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

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.)


Further reading

  1. Floor Function
  2. Base Converter

Source: Message 22 (members only) in the mathemagician Yahoo! Group

Back to top