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)$?

65 Views Asked by At

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)$$

1

There are 1 best solutions below

2
On

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.