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

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

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.

• The inequality $\lceil x \rceil < x+1$ is stronger than $\lceil x \rceil \leq x+1$, but both are valid. – Yuval Filmus Jul 1 at 16:49

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

• AFAIK the contradiction proves that the inequality is wrong isn't it. – Sachin Bahukhandi Jul 1 at 15:28
• No, the inequality is correct. – Yuval Filmus Jul 1 at 15:31
• Okay but the chapter floors and ceilings gave a different perspective on floors and ceilings. – Sachin Bahukhandi Jul 1 at 15:36
• @SachinBahukhandi $a \leq b$ is usually defined as $(a < b) \lor a = b$. Hence to show $a = b$ or $a < b$ is enough to show $a \leq b$. – Novicegrammer Jul 1 at 16:30
• You mean that $a \leq b$ follows from $a < b$, or from $a = b$. In particular, if we know that $a < b$, then it follows that $a \leq b$. – Yuval Filmus Jul 1 at 16:48