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

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

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.

  • $\begingroup$ Sorry about that, when d=1, just delete the that term (make it equal to 0) $\endgroup$ – Mayoi Oct 9 '18 at 4:18
  • $\begingroup$ 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. $\endgroup$ – Mayoi Oct 9 '18 at 6:24

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.