1
$\begingroup$

The problem is to prove that for integers $a,b$ with $b > 0$ $$\left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor = \left\lfloor \frac{a}{b^2} \right\rfloor.$$

I did this by obtaining an inequality both ways. First $$k = \left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor \leq \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \leq \frac{a}{b^2}. $$ Since $k$ is an integer,$$\left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor \leq \left\lfloor \frac{a}{b^2} \right\rfloor.$$ Then $$\left\lfloor \frac{a}{b^2} \right\rfloor = \left\lfloor \frac{nb^2 +r}{b^2} \right\rfloor,$$ with $0 \leq r < b^2$ an integer. $$k' = \left\lfloor \frac{nb^2 +r}{b^2} \right\rfloor = n = \frac{1}{b} \left\lfloor nb \right\rfloor \leq \frac{1}{b} \left\lfloor nb + \frac{r}{b} \right\rfloor = \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor.$$ Since $k'$ is an integer $$\left\lfloor \frac{a}{b^2} \right\rfloor \leq \left\lfloor \frac{1}{b} \left\lfloor \frac{a}{b} \right\rfloor \right\rfloor $$ and we are done.

This is the first problem of the course and considering that, this solution feels insanely difficult. Is there an easier way to do this?

$\endgroup$
1
$\begingroup$

Is there an easier way to do this?

How about the following way?

There exist integers $m,r$ such that $$a=bm+r\quad\text{and}\quad 0\le r\lt b$$ from which $$bm\le bm+r\lt b+bm\implies \frac mb\le \frac{bm+r}{b^2}\lt \frac{m+1}{b}$$ follows.

Since there is no integer $n$ such that $$\frac mb\lt n\lt \frac{m+1}{b}$$ we get $$\left\lfloor\frac{a}{b^2}\right\rfloor=\left\lfloor\frac{bm+r}{b^2}\right\rfloor=\left\lfloor\frac mb\right\rfloor=\left\lfloor\frac 1b\left\lfloor\frac ab\right\rfloor\right\rfloor$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.