1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice proof. Thank you! $\endgroup$ – uttamkhanal Sep 20 '16 at 5:29
  • $\begingroup$ @nitrogen: You’re welcome! $\endgroup$ – Brian M. Scott Sep 20 '16 at 5:29
  • $\begingroup$ Hi, I have one problem that has been bugging me, can you manage some time any time you want so that we can discuss on chat(problem is related to number theory, I had posted the same question here, but I don't understand the answer). $\endgroup$ – uttamkhanal Sep 20 '16 at 5:30
  • $\begingroup$ @nitrogen: Can you give me a link to the question here? I’ll be going to bed pretty soon, but that way I can at least take a quick look now. $\endgroup$ – Brian M. Scott Sep 20 '16 at 5:36
  • $\begingroup$ math.stackexchange.com/questions/1324821/… $\endgroup$ – uttamkhanal Sep 20 '16 at 5:50

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.