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.
2 Answers
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$ It doesn't, but for the special case $m=an$ we have $n\mid an$. $\endgroup$– pshmath0Commented Feb 2, 2014 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$ Commented Feb 2, 2014 at 16:44
-
$\begingroup$ Could you please provide a source/proof for this identity? $\endgroup$– Qiang LiCommented Dec 4, 2016 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$– mathCommented Jan 6, 2017 at 1:22