How to prove floor identities?

I'm trying to prove rigorously the following:

$\lfloor x/a/b \rfloor$ = $\lfloor \lfloor x/a \rfloor /b \rfloor$ for $a,b>1$

So far I haven't gotten far. It's enough to prove this instead

$\lfloor z/c \rfloor$ = $\lfloor \lfloor z \rfloor /c \rfloor$ for $c>1$

since we can just put $z=\lfloor x/a \rfloor$ and $c=b$.

Solution 1:

This theorem is not true if $b$ is not an integer. Take $x=b=1.5$ and take $a=1$.

If $b$ is an integer, this follows from the rule $$\left\lfloor \frac{y}{b}\right\rfloor = \left\lfloor \frac{\lfloor y \rfloor}b\right\rfloor$$

Setting $y=\frac x a$.

Showing this rule, then, suffices.

Let $y = \lfloor y \rfloor + \{y\}$, where $0\leq \{y\} < 1$.

Use division algorithm to write $\lfloor y \rfloor = qb + r$ with $0\leq r <b$.

The $\frac{\lfloor y \rfloor} b = q + \frac{r}{b}$, and $0\leq \frac{r}{b} <1$, so

$$\left\lfloor \frac{\lfloor y \rfloor}b\right\rfloor = q$$

On the other hand, since $[y]< (q+1)b$, since $0\leq\{y\}<1$, then $y = [y]+\{y\}<(q+1)b$.

So $q \leq \frac y b < q+1$ and again $$\left\lfloor \frac{y}{b}\right\rfloor = q $$

Solution 2:

This is best done universally, i.e. using the universal definition of floor

$\begin{align} k\,&\le\, \lfloor x\rfloor \color{#c00}{\iff} k\,\le\, x,\quad {\rm for\ all}\,\ k\in\Bbb Z\\[1em] {\bf Lemma}\qquad\quad\color{#0a0}{\lfloor r/n\rfloor}\,& =\, \lfloor{\lfloor r\rfloor}/n\rfloor\ \ {\rm for}\ \ 0<n\in\Bbb Z,\,\ r\in\Bbb R\\[.6em] {\bf Proof}\qquad\qquad\quad\ \ \ k \,&\le \lfloor{\lfloor r\rfloor}/n\rfloor\\[.4em] \color{#c00}\iff\quad k\ & \le\ \:{\lfloor r\rfloor}/n\\[.4em] \iff\ \ nk\ &\le\ \ \lfloor r\rfloor\qquad {\rm by}\,\ n>0\\[.4em] \color{#c00}\iff\ \ nk\ &\le\,\ \ \ r\qquad\ \ {\rm by}\,\ n\in\Bbb Z\\[.4em] \iff\ \ \ \ k\ &\le\:\ \ \ r/n\quad\ {\rm by}\,\ n>0\\[.4em] \color{#c00}\iff\ \ \ \ k\ &\le\ \ \color{#0a0}{\lfloor r/n\rfloor}\quad {\small\bf QED} \end{align}$

Yours is special case $\ r = x/a,\,\ n = b.$

See the links in comments below for more general (category-theoretic) viewpoints.