# How to prove that $\lceil\lceil x/a\rceil/b\rceil=\lceil x/(ab)\rceil\;\;\forall\text{ real }x\geq0\text{ , }\forall\text{ integer }a,b>0$

While reading a book on algorithms I came across the equality:

$$\lceil \lceil x/a \rceil / b \rceil = \lceil x/(ab) \rceil \ \forall \text{ real }\ x \geq 0\ \text{ and }\ \forall \text{ integer }\ a,b > 0$$.

I tried to prove it out of curiosity with no success. Can someone write down and explain the proof?

Appendix: outline of my attempts

Both $$\lceil \lceil x/a \rceil / b \rceil$$ and $$\lceil x/(ab) \rceil$$ are integers. And I know that the following equality (E1) holds true: $$x \leq \lceil x \rceil < x + 1 \quad \forall \ \text{ real }\ x$$

My idea was to separately substitute $$\lceil \lceil x/a \rceil / b \rceil$$ and $$\lceil x/(ab) \rceil$$ in E1 and show that they are both contained in the same interval and that such interval contains exactly one integer. But I only managed to prove that they are both contained in one interval that contains two integers.

By substituting $$\lceil \lceil x/a \rceil / b \rceil$$ into E1 (and developing some terms):

$$x/(ab) \leq \lceil \lceil x/a \rceil / b \rceil < \lceil x/a \rceil / b + 1$$ and as a result $$x/(ab) \leq \lceil \lceil x/a \rceil / b \rceil < x/(ab) + 1 + 1/b$$

By substituting $$\lceil x/(ab) \rceil$$ into E1 (and developing some terms):

$$x/(ab) \leq \lceil x/(ab) \rceil < x/(ab) + 1$$ and as a result $$x/(ab) \leq \lceil x/(ab) \rceil < x/(ab) + 1 + 1/b$$

So both $$\lceil \lceil x/a \rceil / b \rceil$$ and $$\lceil x/(ab) \rceil$$ are contained in the interval $$[ \ x/(ab), \ x/(ab) + 1 + 1/b \ )$$. If such interval contained only one integer the proof would be completed, but such interval could contain two integers and so I am stuck.

Let $$x = k(ab) +r$$ with $$r \in (0,ab]$$

Then $$\lceil x / a \rceil = \lceil kb + r/a \rceil= kb+r_1$$, where $$r_1 = \lceil r/a \rceil$$.

Since $$r/a \in (0,b]$$ we have $$r_1 \in (0,b]$$

It follows $$\lceil \lceil x/a \rceil / b \rceil = \lceil (kb+ r_1)/b \rceil = \lceil k + r1/b \rceil = k+1$$

This is probably similar to Yorch's answer.

$$\exists\ \text{(unique)}\ k\in\mathbb{Z}\$$ s.t. $$\ kab

Therefore,

$$\ kb< \frac{x}{a}\leq (k+1)b.$$

So,

$$kb+1\leq\bigg{\lceil} \frac{x}{a} \bigg{\rceil}\leq(k+1)b$$

$$\implies k+\frac{1}{b} \leq \frac{\bigg{\lceil} \frac{x}{a} \bigg{\rceil}}{b}\leq k+1.$$

Now, taking the ceiling of everything in the above inequality gives us:

$$\Bigg{\lceil} \frac{\big{\lceil} \frac{x}{a} \big{\rceil}}{b} \Bigg{\rceil} =k+1 =\bigg{\lceil}\frac{ x}{ab} \bigg{\rceil}$$

Letting $$\lceil x\rceil$$ denote the ceiling of $$x$$ for any positive real number $$x$$, we may define the "deficit" of $$x$$ as $$\{x\} := \lceil x\rceil - x$$, which may be thought of as "how far $$x$$ is from the next greatest integer". Any positive integer $$x$$ can therefore be written as $$x=\lceil x\rceil -\{x\}$$. Also, note that $$\{x\}\in [0,1)$$ always.

Consider the deficit of $$x/ab$$, or $$(x/a)/b$$. We may split $$x/a$$ into its own ceiling and deficit, so that this expression becomes $$\lceil x/a\rceil/b - \{x/a\}/b$$. The deficit of the first term equals $$1/b$$ times some number in $$\{0,1,2,...,b-1\}$$ (i.e. the negative remainder of $$\lceil x/a\rceil$$ when divided by $$b$$), and the deficit of the second term equals some number in $$[0,1)$$ times $$1/b$$.

Note that the deficit of the first term and the deficit of the second term must have a sum less than $$1$$. This means that we may write $$x/ab = \lceil \lceil x/a\rceil/b\rceil - d$$ where $$d\in [0,1)$$ ($$d$$ is equal to $$\{\lceil x/a\rceil/b - \{x/a\}/b\}$$). This, in turn, implies that $$\lceil x/ab\rceil = \lceil x/a\rceil/b\rceil$$, as desired.