Evaluating $\sum_{i=0}^{m-1} [ \frac{b + ia}m ]$

777 Views Asked by At

Let $a,b\in\mathbb{Z}$ and $m\in\mathbb{Z}_{>1}$ Evaluate

$[\frac {b}{m}] + [\frac {(b+a)}{m}]+ [\frac {(b+2a)}{m}]+ [\frac {(b+3a)}{m}]+ [\frac {(b+4a)}{m}]+ [\frac {(b+5a)}{m}]+.....+ [\frac {(b+(m-1)a)}{m}] $

Attempt at this solution: I tried to use Hermite Identity.

Assuming that $x = \frac {b}{m} $ and $\frac {1}{n} = \frac {a}{m}$, I got

$[x] + [x + \frac {1}{n}] + [x + \frac {2}{n}] +\dots+ [x + \frac {(n-1)}{n}] = [nx] $

However, $\frac {a}{m}$ is not an integer so I can't use it. I'm stuck what to do?

1

There are 1 best solutions below

6
On

Hermite's identity was generalized for example in Graham, Knuth and Patashnik's famous 'Concrete Mathematics' where they obtained (page $90$ to $94$ so that I won't reproduce it here... pdf files for this book are easier to find than google print previews ;-) so no direct link : everybody should own The Original !) the equation $(3.32)$ : $$\boxed{\displaystyle\sum_{0\le k<m}\left\lfloor\frac{b+ka}m \right\rfloor=d\left\lfloor\frac bd\right\rfloor+\frac{(m-1)(a-1)}2+\frac{d-1}2\quad\text{with}\ \ d=\gcd(m,a)}$$ with $\ m,\ a\ $ positive integers and $\,b\,$ any real.

This allowed them to obtain the nice 'reciprocity law' : $$\sum_{0\le k<m}\left\lfloor\frac{b+k\,a}m \right\rfloor=\sum_{0\le k<a}\left\lfloor\frac{b+k\,m}a \right\rfloor$$