1
$\begingroup$

I have used mathematica to test following equation is true \begin{equation} \sum_{a,b=0}^{m-1} \left[\frac{a+b n}{m}\right] = \frac{n m^2}{2} -\frac{nm}{2} \end{equation} where $[x]$ is the floor function in mathematica

Do you have analytic derivation that how to get the RHS?

Thanks

$\endgroup$
2
  • 3
    $\begingroup$ The sum is the difference of the sum of ratios ourselves and their fractional parts. For a fixed $b$ values $\{(a + bn)/m\}, a = 0, \ldots, m-1$ span $0/m, 1/m, \ldots, (m - 1)/m$. $\endgroup$ May 5, 2022 at 9:18
  • $\begingroup$ @Mikhail Tikhomirow Yes you are right. I had misread, sorry. I will suppress this comment. $\endgroup$ May 7, 2022 at 7:28

1 Answer 1

1
$\begingroup$

For every real number $x$ and every positive integer $m$, one has $$\sum_{a=0}^{m-1} \Big\lfloor x+\frac{a}{m} \Big\rfloor = \lfloor mx \rfloor.$$ To prove this, note that $x$ belongs to the interval $[\lfloor x \rfloor + r/m, \lfloor x \rfloor + (r+1)/m[$ for some $r \in \{0,\ldots,m-1\}$, and then compute both sides of this equality. You get $$\sum_{a=0}^{m-1} (\lfloor x \rfloor + 1_{a+r \ge m}) = m\lfloor x \rfloor + r.$$

Let $n$ be another positive integer. Given $b \in \{0,\ldots,m-1\}$, the last formula applied to $x=bn/m$ yields $$\sum_{a=0}^{m-1} \Big\lfloor \frac{a+bn}{m} \Big\rfloor = bn.$$ Then summing over all $b \in \{0,\ldots,m-1\}$ yields $$\sum_{a,b=0}^{m-1} \Big\lfloor \frac{a+bn}{m} \Big\rfloor = \frac{m(m-1)}{2}n .$$

$\endgroup$
1
  • 2
    $\begingroup$ The formula that Christophe Leuridan uses is more-or-less a special case of the average value relationship for the periodic Bernoulli polynomials, in this case applied to $\mathbb B_1(x)=x-\frac12$. In general, writing $B_n(x)$ for the $n$th Bernoulli polynomial and $\mathbb B_n(x)=B_n\bigl(x-\lfloor x\rfloor\bigr)$ for the version that is periodic modulo 1, we have: $$ \mathbb B_n(mx)= m^{n-1} \sum_{k=0}^{m-1} \mathbb B_n \left(x+\frac{k}{m}\right). $$ From this one can derive many similar formulas. $\endgroup$ Jun 5, 2022 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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