Prove that $\sum_{i = 0}^{n – 1}\lfloor\sqrt{a + \frac{i}{n}}\rfloor = n\lfloor a \rfloor + \lfloor n(a – \lfloor \sqrt a \rfloor) \rfloor$.

Question

Prove that for natural $n$ and all values $a$ such that $\lfloor a \rfloor + 1$ is a perfect square, $$\large \sum_{i = 0}^{n – 1}\left\lfloor\sqrt{a + \frac{i}{n}}\right\rfloor = n\lfloor a \rfloor + \lfloor n(a – \lfloor \sqrt a \rfloor) \rfloor$$

We have that $$\left\lfloor\sqrt{a + \frac{i}{n}}\right\rfloor \ge \lfloor \sqrt a \rfloor, i = \overline{0, n – 1} \implies \sum_{i = 0}^{n – 1}\left\lfloor\sqrt{a + \frac{i}{n}}\right\rfloor \ge n\lfloor \sqrt a \rfloor$$

It can also be seen that $$\sum_{i = 0}^{n – 1}\left\lfloor\sqrt{a + \frac{i}{n}}\right\rfloor > n\lfloor \sqrt a \rfloor \implies \left\lfloor\sqrt{a + \frac{n – 1}{n}}\right\rfloor > \lfloor \sqrt a \rfloor$$

Which means that there exists natural $k$ such that $$\sqrt a < k \le \sqrt{a + \frac{n – 1}{n}} \implies k^2 + \frac{1}{n} \le a + 1 < k^2 + 1 \implies \lfloor
a \rfloor + 1 = k^2$$

Then I'm sure what to do next… But actually, there's a solution to this problem which I have provided. It would be greatly appreciated with the provision that you have feedback about my solution.

Answer 1

Let $\lfloor n(a - \lfloor \sqrt a \rfloor) \rfloor = r$ and $\lfloor a \rfloor + 1 = k^2$, we have that $$k^2 + \frac{r}{n} \le a + 1 < k^2 + \frac{r + 1}{n} \implies \sqrt{a + \frac{n - r - 1}{n}} < k \le \sqrt{a + \frac{n - r}{n}}$$

Deducing that $$\left\lfloor\sqrt{a + \frac{i}{n}}\right\rfloor = \left\{ \begin{align} k - 1 &\text{ where } j < n - r\\ k &\text{ where } n - r \le j \end{align} \right.$$

This implies that $$\sum_{i = 0}^{n - 1}\left\lfloor\sqrt{a + \frac{i}{n}}\right\rfloor = (n - r)(k - 1) + rk = n(k - 1) + r$$

Since $k - 1 = \lfloor\sqrt {a} \rfloor$, $$\sum_{i = 0}^{n - 1}\left\lfloor\sqrt{a + \frac{i}{n}}\right\rfloor = n\lfloor a \rfloor + \lfloor n(a - \lfloor \sqrt a \rfloor) \rfloor$$