Page 171 - Discrete Mathematics and Its Applications

150 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

TABLE 1 Useful Properties of the Floor
and Ceiling Functions.
(n is an integer, x is a real number)
(1a) x = n if and only if n ≤ x< n + 1
(1b) x = n if and only if n − 1 <x ≤ n
(1c) x = n if and only if x − 1 <n ≤ x
(1d) x = n if and only if x ≤ n<x + 1

(2) x − 1 < x ð x ≤ x <x + 1
(3a) −x =− x
(3b) −x =− x
(4a) x + n = x + n
(4b) x + n = x + n

of cells that can be transmitted in 1 minute, we determine the largest integer not exceeding the
quotient when 30,000,000 is divided by 424. Consequently, 30,000,000/424 = 70,754ATM
cells can be transmitted in 1 minute over a 500 kilobit per second connection. ▲

Table 1, with x denoting a real number, displays some simple but important properties of the
floorandceilingfunctions.Becausethesefunctionsappearsofrequentlyindiscretemathematics,
it is useful to look over these identities. Each property in this table can be established using the
definitions of the floor and ceiling functions. Properties (1a), (1b), (1c), and (1d) follow directly
from these definitions. For example, (1a) states that x = n if and only if the integer n is less
than or equal to x and n + 1 is larger than x. This is precisely what it means for n to be the
greatest integer not exceeding x, which is the definition of x = n. Properties (1b), (1c), and
(1d) can be established similarly. We will prove property (4a) using a direct proof.

Proof: Suppose that x = m, where m is a positive integer. By property (1a), it follows that
m ≤ x< m + 1.Adding n to all three quantities in this chain of two inequalities shows that m +
n ≤ x + n<m + n + 1. Using property (1a) again, we see that x + n = m + n = x + n.
This completes the proof. Proofs of the other properties are left as exercises.

The floor and ceiling functions enjoy many other useful properties besides those displayed in
Table 1. There are also many statements about these functions that may appear to be correct, but
actually are not.We will consider statements about the floor and ceiling functions in Examples 29
and 30.
A useful approach for considering statements about the floor function is to let x = n + ,
where n = x is an integer, and , the fractional part of x, satisfies the inequality 0 ≤ < 1.
Similarly, when considering statements about the ceiling function, it is useful to write x = n − ,
where n = x is an integer and 0 ≤ < 1.

1
EXAMPLE 29 Prove that if x is a real number, then 2x = x + x + .
2
Solution: To prove this statement we let x = n + , where n is an integer and 0 ≤ < 1. There
1
are two cases to consider, depending on whether is less than, or greater than or equal to .
2
(The reason we choose these two cases will be made clear in the proof.)