Proof of inequality $\lceil x \rceil \le x+1$

Question

I went through the Master Theorum extension for floors and ceiling section 4.6.2 in the book Introduction to Algorithms

It had the following statement:

Using the inequality $\lceil x \rceil \le x+1$

But I haven't seen the inequality anywhere and could not understand the verifiability of inequality.

Instead the Chapter Floors and ceilings defined floors and ceilings as:

$$x-1 \lt \lfloor x \rfloor \le x \le \lceil x \rceil \lt x+1 $$

Please clear my doubt over this.

On how to use this identity and which identity to be considered when because both of them define completely different inequalities.

Thank you.

Answer 1

The definition of $\lceil x \rceil$ is:

$\lceil x \rceil$ is the minimal integer $n$ such that $n \geq x$.

(The existence of such an integer makes the reals an Archimedean field.)

Let us assume, for the sake of contradiction, that $\lceil x \rceil \geq x + 1$. Then $\lceil x \rceil - 1 \geq x$. Since $\lceil x \rceil - 1$ is also an integer, this contradicts the definition of $\lceil x \rceil$. Thus $\lceil x \rceil < x + 1$.

It is also easy to check that the inequality is tight, in the sense that $1$ cannot be replaced by any smaller $\theta$. Indeed, if $\theta = 1 - \epsilon$ for $\epsilon \in (0,1)$, then $\lceil \epsilon \rceil = 1 = \epsilon + \theta$.