4
$\begingroup$

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

  • 0
    Also, b>1 is stricter than needed; $b=1$ trivially works, too.2012-07-19

3 Answers 3

6

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 .

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 $

3

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

$\rm\qquad\qquad\qquad\qquad\ \ \ k\,\le\, \lfloor x\rfloor \color{#c00}{\iff} k\,\le\, x,\quad {\rm for\ all}\,\ k\in\Bbb Z$

Lemma $\rm\qquad\quad\color{#0a0}{\lfloor r/n\rfloor}\, =\, \lfloor{\lfloor r\rfloor}/n\rfloor\ \ $ for $\rm\ \ 0

Proof $\rm\quad\quad\quad\quad\quad \ \ \ k\ \le \lfloor{\lfloor r\rfloor}/n\rfloor$

$\rm\quad\quad\quad\quad\quad\color{#c00}\iff\quad k\ \le\ \:{\lfloor r\rfloor}/n$

$\rm\quad\quad\quad\quad\quad\iff\ \ nk\ \le\ \ \lfloor r\rfloor\qquad\!\! by\,\ n>0$

$\rm\quad\quad\quad\quad\quad\color{#c00}\iff\ \ nk\ \le\,\ \ \ r\qquad\, by\,\ n\in\Bbb Z$

$\rm\quad\quad\quad\quad\quad\iff\ \ \ \ k\ \le\:\ \ \ r/n\quad by\,\ n>0 $

$\rm\quad\quad\quad\quad\quad\color{#c00}\iff\ \ \ \ k\ \le\ \ \color{#0a0}{\lfloor r/n\rfloor}\quad {\bf QED} $

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

  • 1
    @Marnix I've never heard that term before. Perhaps it is specific to computer science. If you want to view it more generally one can use ideas from category theory, viz. that ceiling,floor are [left,right adjoints](http://math.stackexchange.com/a/6783/242) to the inclusion $\,\Bbb Z\subset \Bbb R,\,$ and [Yoneda's Lemma](http://math.stackexchange.com/questions/149376/excessive-use-of-the-yoneda-lemma). Such viewpoints are mentioned [numerous times here.](http://www.google.com/search?q=site%3Amath.stackexchange.com+%28ceiling+OR+floor%29+%28yoneda+OR+adjoint+OR+adjunction+OR+universal%29)2014-01-30
1

Let $\lfloor x/a \rfloor$ = c(say)=>x=ca+d 0≤d

Let $\lfloor c/b \rfloor$=e(say)=>c=be+f 0≤f

=>x=ca+d=(be+f)a+d=abe+af+d.

$\frac{x}{a}$=be+f+ $\frac{d}{a}$

$\frac{\frac{x}{a}}{b}$=e+$\frac{f}{b}$+$\frac{d}{ab}$

=>$\lfloor x/a/b \rfloor$ = e = $\lfloor c/b \rfloor$ = $\lfloor \lfloor x/a \rfloor /b \rfloor$