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

  • 1
    Just to say, it's not homework.2012-07-19
  • 0
    hint: Start with $x=qa+r$ and $q=q'b+r'$ ($0\le r 2012-07-19
  • 3
    @hermionestranger You might also like to note that in the statement of the problem, we require $a$ and $b$ to be integers, as the result is not true otherwise.2012-07-19
  • 0
    @OldJohn Actually, you just need $b$ to be an integer.2012-07-19
  • 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
    +1 for the nice proof technique $\;\langle \forall k :: k \leq E \iff k \leq F \rangle \iff E = F\;$ (assuming $\;k,E,F\;$ are all integers, or all reals). That was unknown to me, and in retrospect blindingly obvious. This should have been the accepted answer. Thanks!2014-01-23
  • 0
    I just found Dijkstra's [EWD1315](http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1315.html), which states that such proofs are known as "proofs by indirect equality".2014-01-30
  • 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$