janmr blog

Useful Properties of the Floor and Ceil Functions

This articles explores some basic properties of the integer functions commonly known as floor and ceil. Most of the statements may seem trivial or obvious, but I, for one, have a tendency to forget just how exact you can be when it comes to expressions/equations where floor or ceil functions appear.

First, the definitions:

  • = the greatest integer less than or equal to ,
  • = the least integer greater than or equal to ,

for every real number .

Equality

What can we say about and if or ? First of all, we obviously have if and only if is an integer. Let us now consider the floor function . With some real number we have , easily seen from the definition. Now let and assume which is equivalent to . But then cannot be the greatest integer less than or equal to so we have a contradiction. Since was chosen arbitrarily we have for all . Similar considerations can be made for the ceil function and we get the important inequalities:

At the same time, we have the right-going implications of the following statements ( is a real number and an integer):

Let us show the fourth left-going implication. Assume and set . We then have from which we get and , so . The remaining three left-going implication can be proved in much the same way.

From the statements above we can show some useful equalities:

so for all , and

so for all integer . Naturally, the similar also holds.

Inequalities

We now consider what can be said when inequalities are involved. Let be some real number and an integer. We then have the following:

All we need to show these are and from the previous section, and the fact that is equivalent to when and are integers. Consider, for instance, the third statement from above. If then we have , which implies . On the other hand, if then because . The remaining statements are shown in a similar manner.

Some Increasing Functions

Certain functions have special properties when used together with floor and ceil. Such a function must be continuous and monotonically increasing and whenever is integer we must have that is integer. An example could be . Note that being continuous and monotonically increasing ensures a well-defined inverse . One of the requirements can then be formulated as must be integer for all integer .

Using the results of the previous sections we get

Similar derivations can be shown for and we have

for this class of functions. For we thus have

Fractions

The result of the previous section also applies to for integer and . The positivity of ensures that is monotonically increasing and is clearly integer for integer . We now have

From these equalities we have the special cases

for integer and positive .

Let us now consider for integer and . We get

which provides an interval of integers for the numerator . Similarly for the ceil function,

When applying floor or ceil to rational numbers, one can be derived from the other. Since can be rewritten as we get

and similarly

Logarithms

Let be the logarithm of , base (, , ). We first set for integer , base or being the most common. Again, we can apply the theorem from earlier; is continuous and monotonically increasing and is integer for integer , so we have

for integer and .

We conclude with some straightforward, but quite useful, statements:

and

for integer and all , .

References

Most of the material presented in this article can be found in some form in Concrete Mathematics by R. L. Graham, D. E. Knuth, and O. Patashnik, and in The Art of Computer Programming, Volume 1, by Donald E. Knuth.

The Wikipedia page Floor and ceiling functions furthermore lists a lot of properties (very few proofs or derivations, though).