# Prove that $\left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right| \le \sqrt{2n}$.

For all positive integers $$n$$, prove that $$\large \left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} + \left\{\frac{n}{3}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right| \le \sqrt{2n}$$

This is the last problem of a book I (wrongly) stole from the shelves from our class. And there definitely were shortcuts taken.

I also don't really understand the last part $$[\cdots ]\le \frac{m - 2}{2} + \frac{n}{m} < \frac{\sqrt{2n} - 1}{2} + \sqrt{\frac{n}{2}} < 2n$$. Could someone please explain?

Moreover, the answer is lengthy, at least to me. So if you have any other solution that is shorter, please answer below and I would be appreciated.

• So your question is to explain a part of your answer? Sep 6, 2019 at 16:53
• I forgot to mention if any other people have a better solution. Sep 6, 2019 at 16:54
• If you don't understand a part of the proof from the book then you should post that as the question, not as an answer. Sep 6, 2019 at 16:55
• what is the name of the book? Sep 6, 2019 at 19:16
• "Chuyên đề bồi dưỡng học sinh giỏi Toán Trung hoc Phổ Thông - Số Học" by Hà Huy Khoái. Sep 7, 2019 at 4:50

Let $$m = \lfloor\sqrt{2n} + 1\rfloor$$. We have that $$\left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} + \left\{\frac{n}{3}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right|$$

equals the absolute value of

$$\underbrace{\left(\left\{\frac{n}{1}\right\} + \left\{\frac{n}{2}\right\} - \left\{\frac{n}{3}\right\} + \cdots - (-1)^{m - 1}\left\{\frac{n}{m - 1}\right\}\right)}_{A}$$

$$- (-1)^m\underbrace{\left(\frac{n}{m} + \frac{n}{m + 1} - \frac{n}{m + 2} + \cdots + (-1)^{n - m}\frac{m}{n}\right)}_{B}$$

$$+ (-1)^m\underbrace{\left(\left\lfloor\frac{n}{m}\right\rfloor + \left\lfloor\frac{n}{m + 1}\right\rfloor - \left\lfloor\frac{n}{m + 2}\right\rfloor + \cdots + (-1)^{n - m}\left\lfloor\frac{n}{n}\right\rfloor\right)}_{C}$$

Going through each term, we have that

$$- \left(\left\{\dfrac{n}{2}\right\} + \left\{\dfrac{n}{4}\right\} + \left\{\dfrac{n}{6}\right\} + \cdots\right) \le A \le \left\{\dfrac{n}{1}\right\} + \left\{\dfrac{n}{3}\right\} + \left\{\dfrac{n}{5}\right\} + \cdots$$

with the expressions on the left- and right-hand side having $$\left\lfloor\dfrac{m - 1}{2}\right\rfloor$$ and $$\left\lfloor\dfrac{m}{2}\right\rfloor$$ respectively.

(It should be also noted that $$\left\{\dfrac{n}{1}\right\} = 0$$.)

For all $$\left\{\dfrac{n}{p}\right\}$$ $$(p \in \mathbb Z^+, 1 \le p \le m)$$, we have that $$\left\{\dfrac{n}{p}\right\} \le \dfrac{p - 1}{p} \le \dfrac{m - 2}{m - 1}$$

$$\implies |A| \le \left\lfloor\frac{m - 1}{2}\right\rfloor \cdot \dfrac{m - 2}{m - 1} \le \dfrac{m - 2}{2}$$

It is also evident that $$0 \le \left(\frac{m}{n} - \frac{n}{m + 1}\right) + \left(\frac{n}{m + 2} - \frac{n}{m + 3}\right) + \cdots$$

$$= B = \frac{m}{n} - \left(\frac{n}{m + 1} - \frac{n}{m + 2}\right) - \cdots \le \dfrac{n}{m}$$

and $$0 \le \left(\left\lfloor\frac{m}{n}\right\rfloor - \left\lfloor\frac{n}{m + 1}\right\rfloor\right) + \left(\left\lfloor\frac{n}{m + 2}\right\rfloor - \left\lfloor\frac{n}{m + 3}\right\rfloor\right) + \cdots$$

$$= B = \left\lfloor\frac{m}{n}\right\rfloor - \left(\left\lfloor\frac{n}{m + 1}\right\rfloor - \left\lfloor\frac{n}{m + 2}\right\rfloor\right) - \cdots \le \left\lfloor\dfrac{n}{m}\right\rfloor \le \dfrac{n}{m}$$

$$\implies \left|\left\{\frac{n}{1}\right\} - \left\{\frac{n}{2}\right\} + \left\{\frac{n}{3}\right\} - \cdots - (-1)^n\left\{\frac{n}{n}\right\}\right| = |A - (-1)^mB + (-1)^mC|$$

$$\le \frac{m - 2}{2} + \frac{n}{m} < \frac{\sqrt{2n} - 1}{2} + \sqrt{\frac{n}{2}} < 2n$$