# Finding a closed form for a sum involving floor function $\sum\limits_{k=1}^nk\lfloor km/n\rfloor$

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.

• 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 – 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$.

• Why does $m>n \rightarrow n\mid m$? – rhaldryn Feb 2 '14 at 12:22
• It doesn't, but for the special case $m=an$ we have $n\mid an$. – 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}}\ .$$

• That's an interesting Identity, but I can't see how this helps. – SomeStrangeUser Feb 2 '14 at 16:44
• Could you please provide a source/proof for this identity? – Qiang Li Dec 4 '16 at 20:44
• @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? – MathChat Jan 6 '17 at 1:22