Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Fix integer $d>1$, and assume real number $x\in[0,1]$.
I claim the following statement:
$\sum_{k=1}^{dn}\lfloor kx\rfloor=d\sum_{k=1}^n\lfloor kx\rfloor$ is true iff $x\in[0,\frac{1}{dn}]$.

I can check it in various cases, and the if-direction is obvious. But my combinatorics skills are not sharp, so is there a counterexample?

share|cite|improve this question
up vote 2 down vote accepted

You must have $x \in \left[0,\frac{1}{dn}\right)$, for if $x = \frac{1}{dn}$, then the left hand side is $1$, and the right hand side is $0$.

Generally, if $\frac{1}{dn} \leqslant x < \frac{1}{n}$, then

$$d\sum_{k=1}^n \lfloor kx\rfloor = 0 < \lfloor dnx\rfloor \leqslant \sum_{k=1}^{dn} \lfloor kx\rfloor,$$

so in that case you don't have equality. And if $x \geqslant \frac1n$, then you have

$$\begin{align} \sum_{k=1}^{dn} \lfloor kx\rfloor - d\sum_{k=1}^n \lfloor k\rfloor &= \sum_{j=0}^{d-1} \left(\sum_{k=1}^n \left(\lfloor (k+jn)x\rfloor - \lfloor kx\rfloor\right)\right)\\ &\geqslant\sum_{j=0}^{d-1} \sum_{k=1}^n\left(\lfloor kx + j\rfloor - \lfloor kx\rfloor\right)\\ &\geqslant \sum_{j=0}^{d-1} nj\\ &= n\frac{d(d-1)}{2}\\ &> 0. \end{align}$$

share|cite|improve this answer
@DanielFisher, if in addition I have the starting value to be scaled by $d$, i.e. $\sum^{dn}_{k=dk_0}$ and $d\sum^n_{k=k_0}$, do we stumble across a problem? – Chris Gerig Oct 24 '13 at 0:18
One problem is the number of summands. $\sum_{k=dk_0}^{dn}$ gives $d(n-k_0+1)+1$ values, $\sum_{k=k_0}^n$ gives $(n-k_0+1)$ values, so if the terms scaled exactly with $d$, you'd have an extra term. Depending on how that is handled, the range for which both sums have the same value ($0$) may be changed slightly ($x \in \left[0,\frac{1}{dn-1}\right)$ if the $k = dn$ term is omitted), but the strict inequality remains for larger $x$. – Daniel Fischer Oct 24 '13 at 8:12
@DanielFisher, Oh sorry there's a typo. It should be $\sum^{dn}_{k=dk_0+1}$ and $d\sum^{n}_{k=k_0+1}$. Not sure how much this affects your statement, but I don't see exactly how dropping the $k=dn$ term gives us this new range (which I unfortunately can't drop). Ultimately I'm trying to take the original equality that I wrote in the question, and subtract from it the same equality but with smaller $n$. – Chris Gerig Oct 24 '13 at 8:52
If you only sum to $dn-1$, the largest term is $\lfloor (dn-1)x\rfloor$, for $x < \frac{1}{dn-1}$, that is $0$, hence all terms are $0$. But since you keep the upper limit and change the lower limit, that's not relevant. By the way, I mixed up the counts in the previous comment, not yet fully awake. I'm not sure I understand what you're trying to do. You take $\sum_{k=1}^{dn} \lfloor kx\rfloor = d\sum_{k=1}^n \lfloor kx\rfloor$ for $0 \leqslant x < \frac{1}{dn}$, and then subtract $\sum_{k=1}^{dm}\lfloor kx\rfloor = d\sum_{k=1}^m\lfloor kx\rfloor$ from it, for some $m < n$? And then? – Daniel Fischer Oct 24 '13 at 9:03
Ah no sorry, I'm looking for the true range of x after I form the new 'equality'. – Chris Gerig Oct 24 '13 at 9:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.