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