unique floor value proof

Question

Prove that $\lfloor \frac{n}{i}\rfloor - \lfloor \frac{n}{i+1}\rfloor \ge 1$, if $i \le \lfloor\sqrt n\rfloor$ and $1 \le i \le n$

I think I had seen the proof somewhere in this website, but I can't find correct keywords to search the question.

Answer 1

We have

$$\left\lfloor\frac{n}i\right\rfloor-\left\lfloor\frac{n}{i+1}\right\rfloor\ge 1\tag{1}$$

if and only if there is an integer $m$ such that

$$\frac{n}{i+1}<m\le\frac{n}i$$

or, equivalently, such that

$$mi\le n<m(i+1)\;.\tag{2}$$

Suppose that $1\le i\le\left\lfloor\sqrt{n}\right\rfloor$, and let $m=\left\lfloor\frac{n}i\right\rfloor$. Then

$$mi=\left\lfloor\frac{n}i\right\rfloor i\le n\;.$$

Moreover, $\frac{n}i<m+1$, so

$$n<(m+1)i=mi+i\le mi+\sqrt{n}=mi+\frac{n}{\sqrt{n}}\le mi+\frac{n}i\;,$$

and since $mi+i$ is an integer we must have

$$n<mi+i\le mi+\left\lfloor\frac{n}i\right\rfloor=mi+m=m(i+1)\;.$$

Thus, $(2)$ holds, and therefore $(1)$ holds.