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$

Question

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.

Answer 1

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$

Answer 2

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.

Answer 3

This is probably similar to Yorch's answer.

$\exists\ \text{(unique)}\ k\in\mathbb{Z}\ $ s.t. $$\ kab<x\leq (k+1)ab.$$

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