# summation of floor function

I need to calculate $$\sum\limits_{k=0}^{\lfloor(b-a)/a\rfloor}\left\lfloor\frac{a+ka-1}{2} \right\rfloor$$ For example for $a=3$ and $b=7$ we have $$\left\lfloor\frac{2}{2}\right\rfloor+\left\lfloor\frac{5}{2}\right\rfloor=1+2=3$$ Can a general answer be reached?

-
Also posted to MO, mathoverflow.net/questions/96388/summation-of-floor-function, where it will undoubtedly be closed very soon. – Gerry Myerson May 8 '12 at 23:41

You want $$\sum_{a\le ka\le b}\left\lfloor\frac{ka-1}2\right\rfloor=\sum_{k=1}^m\left\lfloor\frac{ka-1}2\right\rfloor\;,$$ where $m=\lfloor b/a\rfloor$. If $a$ is even, $ka-1$ is always odd, and $$\left\lfloor\frac{ka-1}2\right\rfloor=\frac{ka}2-1\;,$$ so \begin{align*} \sum_{k=1}^m\left\lfloor\frac{ka-1}2\right\rfloor&=\sum_{k=1}^m\left(\frac{ka}2-1\right)\\ &=\frac{a}2\sum_{k=1}^mk-m\\ &=\frac{am(m+1)}4-m\;. \end{align*}

If $a$ is odd,

$$\left\lfloor\frac{ka-1}2\right\rfloor=\begin{cases} \frac{ka}2-1,&\text{if }k\text{ is even}\\\\ \frac{ka-1}2=\left(\frac{ka}2-1\right)+\frac12,&\text{if }k\text{ is odd}\;. \end{cases}$$

Let $c$ be the number of odd integers in $\{1,\dots,m\}$; then

\begin{align*} \sum_{k=1}^m\left\lfloor\frac{ka-1}2\right\rfloor&=\frac{c}2+\sum_{k=1}^m\left(\frac{ka}2-1\right)\\ &=\frac{c}2+\frac{am(m+1)}4-m\;. \end{align*}

Finally, $c=\lceil m/2\rceil$, so

$$\sum_{k=1}^m\left\lfloor\frac{ka-1}2\right\rfloor=\begin{cases} \frac{am(m+1)}4-m,&\text{if }a\text{ is even}\\\\ \frac{\lceil m/2\rceil}2+\frac{am(m+1)}4-m,&\text{if }a\text{ is odd}\;. \end{cases}$$

-

Here are some ideas that should enable you to answer the question. We have $$\left\lfloor \frac{x}{2} \right\rfloor = \begin{cases} \frac{x}{2} & \text{if } x \text{ is even}, \\ \frac{x-1}{2} & \text{if } x \text{ is odd}. \end{cases}$$ Therefore $$\sum_{k=0}^{\lfloor (b-a)/a \rfloor} \left\lfloor \frac{a+ka-1}{2} \right\rfloor = \sum_{k=0}^{\lfloor (b-a)/a \rfloor} \frac{a+ka-1}{2} - \sum_{\substack{k=0\\k\text{ odd}}}^{\lfloor (b-a)/a \rfloor} \frac{1}{2}.$$ The first sum you can calculate using a formula. The second sum depends on the number of odd integers in the given range.

-

$S=\sum\limits_{k=0}^{\lfloor(b-a)/a\rfloor}\left\lfloor\dfrac{a+ka-1}{2} \right\rfloor=\sum\limits_{k=1}^{\lfloor\frac{b}{a}\rfloor}\left\lfloor\dfrac{ka-1}{2}\right\rfloor$

If $\quad a=2c\quad$ then

$S=\sum\limits_{k=1}^{\left\lfloor\frac{b}{2c}\right\rfloor}\left\lfloor kc -\dfrac{1}{2}\right\rfloor=\sum\limits_{k=1}^{\left\lfloor\frac{b}{2c}\right\rfloor}(kc -1)=\dfrac{c}{2}\left\lfloor\dfrac{b}{2c}\right\rfloor\left(\left\lfloor\dfrac{b}{2c}\right\rfloor+1\right)-\left\lfloor\dfrac{b}{2c}\right\rfloor$

If $\quad a=2c+1\quad$ then

$S=\sum\limits_{k=1}^{\left\lfloor\frac{b}{2c+1}\right\rfloor}\left\lfloor kc +\dfrac{k-1}{2}\right\rfloor=c\sum\limits_{k=1}^{\left\lfloor\frac{b}{2c+1}\right\rfloor}k +\sum\limits_{k=0}^{\left\lfloor\frac{b}{2c+1}\right\rfloor-1}\left\lfloor\dfrac{k}{2}\right\rfloor=\dfrac{c}{2}\left\lfloor\dfrac{b}{2c+1}\right\rfloor\left(\left\lfloor\dfrac{b}{2c+1}\right\rfloor+1\right)+\left\lfloor\dfrac{\left\lfloor\frac{b}{2c+1}\right\rfloor-1}{2}\right\rfloor\left\lfloor\dfrac{\left\lfloor\frac{b}{2c+1}\right\rfloor}{2}\right\rfloor$

Combine two formular in one, we get:

$\boxed{S=\dfrac{1}{2}\left\lfloor\dfrac{a}{2}\right\rfloor\left\lfloor\dfrac{b}{a}\right\rfloor\left(\left\lfloor\dfrac{b}{a}\right\rfloor+1\right)+\left(\left\lfloor\dfrac{b-a}{2a}\right\rfloor\left\lfloor\dfrac{b}{2a}\right\rfloor+\left\lfloor\dfrac{b}{a}\right\rfloor\right)\left(a-2\left\lfloor\dfrac{a}{2}\right\rfloor\right)-\left\lfloor\dfrac{b}{a}\right\rfloor}$

-