Alternating sum of floor/ceiling function

176 Views Asked by At

Let $(n,l)=1$, there are formulas for the sum of floor and ceiling functions:

$$\sum_{i=1}^{l-1}\left\lfloor \frac{in}{l}\right\rfloor =\frac{1}{2}(n-1)(l-1)$$

and

$$\sum_{i=1}^{l-1}\left\lceil \frac{in}{l}\right\rceil =\frac{1}{2}(n+1)(l-1)$$

For the alternating sum $\displaystyle S(l,n)=\sum_{i=1}^{l-1}(-1)^{i+1}\left\lceil \frac{in}{l}\right\rceil $, is there a way to obtain a formula for $S(l,n)$?

Conjecture: Let $\displaystyle w(j,h)=\sum_{k=1}^{j-1}(-1)^{k+1}\left\lceil\frac{kh}{j}\right\rceil+h-1$, then $\displaystyle \sum_{j=1\ odd}^{h-1}w(j,h)>0$.

1

There are 1 best solutions below

3
On

I can come up with a formula for $S(2m,n)$. First, let's start with $$\frac{in}{l}+\frac{(l-i)n}{l}=\frac{ln}l=n$$ We could also calculate the sum as $$\frac{in}l+\frac{(l-i)n}l=\left\lceil\frac{in}l\right\rceil-\alpha+\left\lceil\frac{(l-i)n}l\right\rceil-\beta$$ where $\alpha$ is 1 minus the fractional part of $\frac{in}l$ and $\beta$ is 1 minus the fractional part of $\frac{(l-i)n}l$. Since $in$ and $(l-i)n$ cannot be multiples of $l$, these fractional parts are greater than 0 and less than 1. So $0<\alpha+\beta<2$. If we set the results of both equations equal to one another, since $n$ is an integer, the other value must be an integer as well, meaning that $\alpha+\beta$ must also be an integer. Combine this with the inequality and we have $\alpha+\beta=1$. This leads to $$\left\lceil\frac{in}l\right\rceil+\left\lceil\frac{(l-i)n}l\right\rceil-1=n$$ $$\left\lceil\frac{in}l\right\rceil+\left\lceil\frac{(l-i)n}l\right\rceil=n+1$$ Now that this is established, we can rewrite the summation \begin{align} S&=\sum_{i=1}^{2m-1}(-1)^{i+1}\left\lceil\frac{in}{2m}\right\rceil\\ &=\sum_{i=1}^{i+1}(-1)^{2m-i+1}\left\lceil\frac{(2m-i)n}{2m}\right\rceil\\ &=\sum_{i=1}^{2m}(-1)^{2(m-i)+i+1}\left\lceil\frac{(2m-i)n}{2m}\right\rceil\\ &=\sum_{i=1}^{2m-1}(-1)^{i+1}\left\lceil\frac{(2m-i)n}{2l}\right\rceil \end{align} The order of summation was reversed. Now we add both sums together to get \begin{align} 2S&=\sum_{i=1}^{2m-1}(-1)^{i+1}\left\lceil\frac{in}{2m}\right\rceil+\sum_{i=1}^{2m-1}(-1)^{i+1}\left\lceil\frac{(2m-i)n}{2m}\right\rceil\\ &=\sum_{i=1}^{2m-1}(-1)^{i+1}\left(\left\lceil\frac{in}{2m}\right\rceil+\left\lceil\frac{(2m-i)n}{2m}\right\rceil\right)\\ &=\sum_{i=1}^{2m-1}(-1)^{i+1}(n+1)\\ &=n+1\end{align} Now just divide by $2$ to get $S(2m,n)=\frac{n+1}2$. This method can also similarly prove the other 2 formulas you listed. But it breaks down when $l$ is odd and the signs don't match.