# How to simplify this equality: $\sum_{i=1}^{n}\sum_{d\mid i} (\lfloor \frac{i}{d+1} \rfloor + \lfloor \frac{i}{d-1} \rfloor)$?

By guessing, I obtained: $$\sum_{i=1}^{n}\sum_{d\mid i} (\lfloor \frac{i}{d+1} \rfloor + \lfloor \frac{i}{d-1} \rfloor)=\sum_{i=1}^{n}(\lfloor \frac{n}{i}\rfloor \lfloor \frac{n}{i+1}\rfloor + \lfloor \frac{n}{i(i+1)}\rfloor)$$But I did not figure out how to prove it. When $$d=1$$, just ignore this term $$\lfloor \frac{i}{d-1} \rfloor$$.

I know how to prove a similar equality, but I am not sure if the two could be generalized to a same form. The equality is: $$\sum_{i=1}^{n}\sum_{d\mid i} (\lfloor \frac{i}{d} \rfloor + \lfloor \frac{i}{d} \rfloor)=\sum_{i=1}^{n}(\lfloor \frac{n}{i}\rfloor \lfloor \frac{n}{i}\rfloor + \lfloor \frac{n}{i}\rfloor)$$

• The right hand sides seem to depend on $d$. Should there be a double sum? – Theo Bendit Oct 9 '18 at 3:06
• @TheoBendit I am sorry, that was a typo – Mayoi Oct 9 '18 at 3:46
• The right hand side is not defined when d=1, which it is for each i. – marty cohen Oct 9 '18 at 4:04

## 1 Answer

Playing around.

$$\begin{array}\\ s_f(n) &=\sum_{i=1}^n \sum_{d|i} f(i, d)\\ &=\sum_{d=1}^n \sum_{k=1}^{[\frac{n}{d}]} f(kd, d) \qquad\text{reversing the order of summation}\\ \end{array}$$

If $$f(i, d) =[\frac{i}{d}]$$, then

$$\begin{array}\\ s_f(n) &=\sum_{d=1}^n \sum_{k=1}^{[\frac{n}{d}]} [\frac{kd}{d}]\\ &=\sum_{d=1}^n \sum_{k=1}^{[\frac{n}{d}]} k\\ &=\sum_{d=1}^n \frac12 [\frac{n}{d}]([\frac{n}{d}]+1)\\ \end{array}$$

which verifies your second equality.

I assume that this is the way you proved it.

If $$f(i, d) =\lfloor \frac{i}{d+1} \rfloor + \lfloor \frac{i}{d-1} \rfloor$$, then

$$\begin{array}\\ s_f(n) &=\sum_{d=1}^n \sum_{k=1}^{[\frac{n}{d}]}\lfloor \frac{kd}{d+1} \rfloor + \lfloor \frac{kd}{d-1} \rfloor\\ \end{array}$$

and I am not sure what you want to happen when $$d=1$$.

So I will leave it at this.

• Sorry about that, when d=1, just delete the that term (make it equal to 0) – Mayoi Oct 9 '18 at 4:18
• I suspect this method does not work. $\sum_{k=1}^{\frac{n}{d}}f_2(kd,d)=\frac{1}{2}\lfloor \frac{n}{d}\rfloor(\lfloor \frac{n}{d}\rfloor+1)$ holds for each d in the second equality, but this is not true for the first one. – Mayoi Oct 9 '18 at 6:24