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

Improve this question
$\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$
    – Mikhail Tikhomirov
    Commented May 5, 2022 at 9:18
  • $\begingroup$ @Mikhail Tikhomirow Yes you are right. I had misread, sorry. I will suppress this comment. $\endgroup$
    – Christophe Leuridan
    Commented May 7, 2022 at 7:28

1 Answer 1

Reset to default
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 .$$

Improve this answer
$\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$
    – Joe Silverman
    Commented Jun 5, 2022 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .