Given integers $m,n$, is there a known closed form for the sum $\sum\limits_{k=1}^nk\lfloor km/n\rfloor$? and if not, is it possible to show there is no closed form for this sum? I've attempted to derive a closed form using the techniques in this question: Formula and proof for the sum of floor and ceiling numbers, with no luck. Any help will be greatly appreciated.

  • $\begingroup$ This could help: If $m$ and $n$ are positive and coprime, then$$\sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor = \frac{1}{2}(m - 1)(n - 1)$$ Source $\endgroup$ – rhaldryn Feb 2 '14 at 12:13

This is only a partial answer. There are three identifiable cases here: $m=n$, $m>n$, and $0<m<n$.

Case 1: $\textbf{m=n:}$ This is the simpler case:

$$S=\sum_{k=1}^n k\lfloor\frac{km}{n}\rfloor = \sum_{k=1}^n k\lfloor k\rfloor=\sum_{k=1}^n k^2=\frac{1}{6}n(n+1)(2n+1),$$ by way of Bernoulli's sum of powers formula. The other two cases are more difficult.

Case 2: $\textbf{m>n:}$ To simplify matters suppose $m=bn$ for some integer $b>1$. Then $$S=\sum_{k=1}^n k\lfloor k\frac{bn}{n}\rfloor = \sum_{k=1}^n k\lfloor k b\rfloor = b\sum_{k=1}^n k^2 = \frac{b}{6}n(n+1)(2n+1).$$

For the more general case, suppose $m=bn+a$ with $1<a<n$ and $b\geq 1$. Then we have $$S=\sum_{k=1}^n k\lfloor \frac{k(bn+a)}{n}\rfloor = \sum_{k=1}^n k\lfloor kb+\frac{ka}{n}\rfloor = b\sum_{k=1}^n k^2+\sum_{k=1}^n k\lfloor\frac{ka}{n}\rfloor,$$ so $$S= \frac{b}{6}n(n+1)(2n+1)+\sum_{k=1}^n k\lfloor\frac{ka}{n}\rfloor,$$ where we see that $0<a/n<1$. Thus the entire problem has been reduced to the third case only, i.e. for when $0<m<n$ (see top of answer)

Case 3: $\textbf{0<m<n:}$ It may be the case that there is a closed form when $\text{gcd}(m,n)=1$.

  • $\begingroup$ Why does $m>n \rightarrow n\mid m$? $\endgroup$ – rhaldryn Feb 2 '14 at 12:22
  • $\begingroup$ It doesn't, but for the special case $m=an$ we have $n\mid an$. $\endgroup$ – Pixel Feb 2 '14 at 12:25

Maybe the following helps:

For given $n\in{\mathbb N}_{\geq1}$ put $\omega:=e^{2\pi i/n}$. Then for any integer $j$ one has $$\left\lfloor{j\over n}\right\rfloor={j\over n}-{n-1\over 2n}+{1\over n}\sum_{\ell=1}^{n-1}{\omega^{j\ell}\over 1-\omega^{-\ell}}\ .$$

  • $\begingroup$ That's an interesting Identity, but I can't see how this helps. $\endgroup$ – SomeStrangeUser Feb 2 '14 at 16:44
  • $\begingroup$ Could you please provide a source/proof for this identity? $\endgroup$ – Qiang Li Dec 4 '16 at 20:44
  • $\begingroup$ @SomeStrangeUser: I'm interested in a closed formula for the sum $\sum\limits_{k=1}^{n-1}k\lfloor \frac{km}{n}\rfloor$ too. Have you found any additional reference for it? Would you have any combinatorial interpretation for it? $\endgroup$ – MathChat Jan 6 '17 at 1:22

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.