Can floor(floor(a/b)/c) ever be different to floor(a/(bc))?

Question

Is there any mathematical proof that the following equality holds true always (across the natural number domain)?

$\lfloor{\frac{\lfloor^a/_b\rfloor}{c}}\rfloor = \lfloor\frac{a}{bc}\rfloor \quad \textrm{for}\ \ \ a,b,c\ \in\ \mathbb{N}$

In other words, I'm looking for proof that there are no values of a, b, and c, for which a two-step integer-truncation division will give a different result than dividing by the product of the two divisors?

Answer 1

$$\left\lfloor{\frac{\lfloor^a/_b\rfloor}{c}}\right\rfloor \ne \left\lfloor\frac{a}{bc}\right\rfloor$$

First we prove the following lemma:

Lemma 1: Let $p>q$ be 2 non-negative real numbers and $r$ a nonzero natural number. If there is no natural number $m$ such that $p>m>q$ then there is no natural number $n$ such that $p/r>n>q/r$

We can prove it using the contrapositive. If there is a natural number $n$ such that$p/r>n>q/r$ then $m=rn$ is such that $p>m>q$. This completes the proof.

When

$$\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor$$ it is easy to see that $$\left\lfloor{\frac{\lfloor^a/_b\rfloor}{c}}\right\rfloor = \left\lfloor\frac{a}{bc}\right\rfloor$$

Next consider the case where $$\frac{a}{b}>\left\lfloor\frac{a}{b}\right\rfloor$$ Obviously there's no natural number between the two. Also $$\frac{a}{bc}>\frac{\lfloor^a/_b\rfloor}{c}$$

and Lemma 1 tells us that there is no natural number between the 2. So we can take the floor of both sides of the inequality to get

$$\left\lfloor{\frac{\lfloor^a/_b\rfloor}{c}}\right\rfloor = \left\lfloor\frac{a}{bc}\right\rfloor$$

This completes the proof.

Answer 2

Given a real number $x$ and an integer $n$, in order to prove $n = \lfloor x \rfloor$ we need to prove two things:

• $n \leq x$, and
• for every integer $m$ with $m \leq x$, we have $m \leq n$.

So, first note that $$ \left\lfloor \frac{\lfloor a/b \rfloor}{c} \right\rfloor \leq \frac{\lfloor a/b \rfloor}{c} \leq \frac{a/b}{c} = \frac{a}{bc}. $$ Next, if $m$ is any integer with $m \leq a/(bc)$, \begin{align} m \leq \frac{a}{bc} &\implies mc \leq a/b \\ &\implies mc \leq \lfloor a/b \rfloor \\ &\implies m \leq \frac{\lfloor a/b \rfloor}{c} \implies m \leq \left\lfloor \frac{\lfloor a/b \rfloor}{c} \right\rfloor. \end{align} Thus: $$ \left\lfloor \frac{\lfloor a/b \rfloor}{c} \right\rfloor = \left\lfloor \frac{a}{bc} \right\rfloor. $$