Prove the following ceiling and floor identities?

Could someone help me prove these identities? I'm completely lost:

$$\begin{align*} &(1)\quad \left\lceil \frac{\left\lceil \frac{x}{a} \right\rceil} {b}\right\rceil = \left\lceil {\frac{x}{ab}}\right\rceil\\\\ &(2)\quad\left\lfloor \frac{\left\lfloor \frac{x}{a} \right\rfloor} {b}\right\rfloor = \left\lfloor {\frac{x}{ab}}\right\rfloor\\\\ &(3)\quad \left\lceil {\frac{a}{b}} \right\rceil \le \frac{a + b - 1}{b}\\\\ &(4)\quad \left\lfloor {\frac{a}{b}} \right\rfloor \le \frac{a - b + 1}{b} \end{align*}$$

Thanks for the help.

Solution 1:

Using the universal properties of floor and ceiling makes such proofs mechanical, e.g.

$\rm {\bf Lemma}\quad\ \lfloor x/(mn)\rfloor = \lfloor{\lfloor x/m\rfloor}/n\rfloor\quad for\ \ \ n > 0 $

$\rm\begin{eqnarray} {\bf Proof}\quad\ &&\rm\ \ k &\,\le&\rm \lfloor{\lfloor x/m\rfloor}/n\rfloor\\ \\ &\iff\ &\rm \ \ k &\,\le&\rm \ \, {\lfloor x/m\rfloor}/n\\ \\ &\iff\ &\rm nk &\,\le&\rm\ \,\lfloor x/m\rfloor \\ \\ &\iff\ &\rm nk &\,\le&\rm\ \ \, x/m \\ \\ &\iff\ &\rm\ \ k &\,\le&\rm\ \ \, x/(mn)\\ \\ &\iff\ &\rm\ \ k &\,\le&\rm\ \lfloor x/(mn)\rfloor \end{eqnarray}$

Solution 2:

You can work directly from the definitions. I’ll do $(2)$ and $(3)$ to illustrate.

$(2)$ First note that you want $a$ and $b$ to be positive. If not, you might have $x=\frac12$ and $a=b=-1$, in which case the lefthand side is $$\left\lfloor-\left\lfloor-\frac12\right\rfloor\right\rfloor=\lfloor-(-1)\rfloor=1\;,$$ and the righthand side is $\left\lfloor\frac12\right\rfloor=0$. You also want them to be integers: if $x=2$ and $a=b=\sqrt2$, the lefthand side is $$\left\lfloor\frac{\lfloor\sqrt2\rfloor}{\sqrt2}\right\rfloor=\left\lfloor\frac1{\sqrt2}\right\rfloor=0\;,$$ and the righthand side is $1$. I will assume, then, that $a$ and $b$ are positive integers.

Let $m=\left\lfloor\dfrac{x}a\right\rfloor$ and $n=\left\lfloor\dfrac{x}{ab}\right\rfloor$. Then $$m\le\frac{x}a<m+1\quad\text{and}\quad n\le\frac{x}{ab}<n+1\;,\tag{1}$$ and you need to show that $\left\lfloor\dfrac{m}b\right\rfloor=n$, i.e., that $$n\le\frac{m}b<n+1\;.\tag{2}$$ Divide the first inequality in $(1)$ by $b$ to get $$\frac{m}b\le\frac{x}{ab}<\frac{m}b+\frac1b\;,$$ where $b\ge 1$. Now what would happen if $(2)$ failed? That would mean that either $\frac{m}b<n$, or $\frac{m}b\ge n+1$. It’s not hard to show that both are impossible. Suppose first that $\frac{m}b<n$. Then $\frac{m}b\le n-\frac1b$. (Why? Use the fact that $m,n$, and $b$ are integers.) Thus, $$\frac{x}{ab}<\frac{m}b+\frac1b\le n\;,$$ contradicting the second inequality in $(1)$. And if $\frac{m}b\ge n+1$, then $$\frac{x}{ab}\ge\frac{m}b\ge n+1\;,$$ again contradicting that inequality. So $(2)$, which is exactly what we set out to prove, must be true.

$(3)$ Let $m=\left\lceil\dfrac{a}b\right\rceil$, so that $m-1<\dfrac{a}b\le m$. Because $a,b$, and $m-1$ are integers, $$\frac{a}b-(m-1)\ge\frac1b\;,$$ and therefore $$m\le\frac{a}b+1-\frac1b=\frac{a+b-1}b\;,$$ which is exactly what we wanted.