How to prove the ceiling relations stated in CLRS Introduction to Algorithms book?

Question

In the book "Introduction to Algorithms", by CLRS, page 54, the following relations are stated (enumeration is mine):

---

For any real number $x\geq 0$ and integers $a,b>0$, $$ \begin{aligned} (1)\qquad\left\lceil\dfrac{\lceil x/a\rceil}{b}\right\rceil&=\left\lceil\dfrac{x}{ab}\right\rceil\\ (2)\qquad\qquad\left\lceil\dfrac{a}{b}\right\rceil&\leq\dfrac{a+(b-1)}{b} \end{aligned} $$

---

I'd like to come up with a proof for these relations, but I'm getting nowhere.

For (1), I understand that I need to somehow prove that, for $m=\lceil x/a\rceil$ and $n=\lceil x/ab\rceil$, it is the case that

$$ \lceil n/b\rceil-1<n/b\leq\lceil n/b\rceil\text{ if and only if }m-1<x/a\leq m $$

I tried manipulating different inequalities but the obstacle I'm facing is that I can't find any useful way to relate $n$ with $m$. Ideally, I imagine that (somehow) I should be able to remove the ceiling signs around $\lceil x/a\rceil$, manipulate the resulting expression to come up with $x/ab$, and then return the ceiling signs to get $\lceil x/ab\rceil$. I don't see how this could be possible, though.

For (2), I started in a similar fasion. Letting $n=\lceil a/b\rceil$, I know from the definition of the ceiling function that $n-1<a/b\leq n$. So, what I want to prove is that $$ n\leq\dfrac{a+b-1}{b} $$ I thought this could be proven in a straighforward fashion using algebra, but the obstacle I'm facing is that the relation has a $\leq$ sign, instead of a $<$ sign (which I can easily obtain from the definition of the ceiling function).

Any tips on how I could get started with these proofs will be very much appreciated.

Answer 1

For (2), consider that

$$ \frac{a + b}{b} = \frac{a}{b} + 1 > \bigg\lceil \frac{a}{b} \bigg\rceil $$

We can "sharpen" this inequality by choosing the largest number less than $a/b + 1$ that could possibly be the value of the ceiling expression. That means that it will have to be an integer for some value of $a/b$.

Since $a/b$ is a fraction with denominator $b$, the difference between it and an integer will have the same denominator. Thus, there will be some $k\in \Bbb Z$ such that

$$ \bigg\lceil \frac{a}{b} \bigg\rceil \leq \frac{a}{b} + \frac{k}{b} $$

We already know $k/b < 1$ and so $k < b$. So we ask: can be $k = b-1$? Well, if $a \equiv 1 \text{ mod } b$, then

$$\frac{a}{b} + \frac{b-1}{b} = \frac{(kb+1) + (b - 1)}{b} = k+1 \in \Bbb Z $$

Thus,

$$ \bigg\lceil \frac{a}{b} \bigg\rceil \leq \frac{a}{b} + \frac{b-1}{b} = \frac{a+b-1}{b}$$

where equality holds iff $a \equiv 1 \text{ mod } b$.

---

For (1):

If $\frac{x}{ab} \in \Bbb Z$, then $x/a \in \Bbb Z$ as well and so $\lceil x/a \rceil = x/a$ and the result is trivial. Similarly, if $b=1$, the result is trivial. From here on out, assume neither is the case.

We have

$$ \bigg\lceil \frac{x}{a} \bigg\rceil < \frac{x}{a} + 1 $$

and so

$$ \frac{\lceil x/a \rceil}{b} < \frac{x}{ab} + \frac{1}{b} $$

There are two cases to consider: $\lceil x/a \rceil / b \in \Bbb Z$ or it's not.

In the former case, we have that

$$ \frac{\lceil x/a \rceil}{b} > \frac{x}{ab} > \frac{\lceil x/a \rceil}{b} - \frac{1}{b} > \frac{\lceil x/a \rceil}{b} - 1 $$

In the latter case, an argument similar to the one for (2) shows that

$$ \bigg\lfloor \frac{\lceil x/a \rceil}{b} \bigg\rfloor \leq \frac{\lceil x/a \rceil}{b} - \frac{1}{b} < \frac{x}{ab} < \frac{\lceil x/a \rceil}{b} <\bigg\lfloor \frac{\lceil x/a \rceil}{b} \bigg\rfloor + 1 $$

In either case, both $\frac{\lceil x/a \rceil}{b}$ and $\frac{x}{ab}$ are in the same interval $(k,k+1]$ for some $k\in\Bbb Z$, i.e.

$$ \bigg\lceil \frac{x}{ab} \bigg\rceil = \bigg\lceil \frac{\lceil x/a \rceil}{b} \bigg\rceil $$

Answer 2

I think I found a proof for (1), but it requires us to first prove the following lemma, which I found in "Concrete Mathematics", by Graham, Knuth and Patashnik, page 71, alongside it's proof (which I'm also posting below). The lemma goes like this:

---

Lemma 1. Let $f$ be any continuous, monotonically increasing function with the special property that: if $f(x)\in\mathbb{Z}$, then $x\in\mathbb{Z}$. Then, we have $\lfloor f(x)\rfloor=\lfloor f(\lfloor x\rfloor)\rfloor$ and $\lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil$, whenever $f(x)$, $f(\lfloor x\rfloor)$ and $f(\lceil x\rceil)$ are defined.

Proof. Only the proof for the ceiling function will be shown, since the proof for the floor function is similar. Let $x$ be any real number in the domain of $f$. By the definition of the ceiling function, we have that $x\leq\lceil x\rceil$.

First, let $x=\lceil x\rceil$. In this case, we have $f(x)=f(\lceil x\rceil)$ and, consecuently, $\lceil f(x)\rceil=\lceil f(\lceil x \rceil)\rceil$. This ends the proof for this case.

Now, let $x<\lceil x\rceil$. This implies that $f(x)<f(\lceil x\rceil)$, since $f$ is monotonically increasing. Consecuently, we have $\lceil f(x)\rceil\leq\lceil f(\lceil x\rceil)\rceil$, since the ceiling function is non-decreasing. Next, we're going to prove that $\lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil$ by developing a contradiction. Assume that $\lceil f(x)\rceil<\lceil f(\lceil x\rceil)\rceil$. We've arrived to the following relation: $$ f(x)\leq\lceil f(x)\rceil<\lceil f(\lceil x\rceil)\rceil. $$ Since $f$ is continuous, there exists a value $x'$ in the domain of $f$ for which the following relation is true: $$ x\leq x'<\lceil x\rceil\text{ and }f(x')=\lceil f(x)\rceil, $$ and by the special property of $f$, we have that $x'\in\mathbb{Z}$. However, there can be no integer that is strictly between $x$ and $\lceil x\rceil$ (since $\lceil x\rceil$ is the minimum integer greater than $x$). Thus, we've reached a contradiction. Therefore, we conclude that $\lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil$. Q.E.D.

---

We can now use Lemma 1 to prove relation (1). Observe that we can define a function $g$ as $$ g(x)=\dfrac{x}{b}. $$ This function is continuous and monotonically increasing (since $x/b$ is a linear function), and also has the special property that $x\in\mathbb{Z}$ if $g(x)\in\mathbb{Z}$ (since the only way for $x/b$ to be an integer is if $x$ is a multiple of $b$). Thus, we can apply Lemma 1 to $g(x/a)$ to get $$ \begin{aligned} \lceil g(x/a)\rceil &= \lceil g(\lceil x/a\rceil)\rceil\\ \therefore\left\lceil\dfrac{x}{ab}\right\rceil &= \left\lceil\dfrac{\lceil x/a\rceil}{b}\right\rceil, \end{aligned} $$ thus proving relation (1).