2
$\begingroup$

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$.

$\endgroup$
9
  • $\begingroup$ Have you computed any examples? Do you have any conjectures? $\endgroup$
    – JBL
    Apr 26 at 1:26
  • $\begingroup$ @JBL Yes I added the conjecture. $\endgroup$ Apr 26 at 2:01
  • 1
    $\begingroup$ If you are actually asking to prove the inequality, then I suggest to move it to another question. If it is just a remark, I am not sure what purpose it serves (you were asked for your "conjectures" or thoughts on the original problem, what you think the resulting formula might be, any ideas, etc, not to generate additional questions) $\endgroup$
    – Sil
    Apr 28 at 14:56
  • 1
    $\begingroup$ Then I suggest to update the original post, you cannot expect anyone to find the "actual" question in a comment to an answer... However changing the question after it was already answered (even though only partially) is not a good practice, so consider asking separate question for the lower bound (I assume you are asking for lower bound that is able to prove the "Conjecture" you mention in the post) $\endgroup$
    – Sil
    Apr 28 at 15:10
  • 1
    $\begingroup$ @Sil Another question is posted here math.stackexchange.com/questions/4688431/… $\endgroup$ Apr 28 at 17:27

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ @Sil Part of the problem was $\gcd(l,n)=1$. Without that, the number you're taking the ceiling of can be an integer and the fractional part becomes zero. It can be accounted for, but it will throw off the result. $\endgroup$
    – Mike
    Apr 26 at 23:08
  • $\begingroup$ Oh I didn't notice that $2m$ and $n$ should be coprime, then your formula makes sense indeed. $\endgroup$
    – Sil
    Apr 27 at 15:17
  • $\begingroup$ Thanks, interesting! When l is odd, I wonder if there is any approximation formula. When $(n,l)=1$, the remainders of $kn$ mod $l$ are all distinct. By assuming that the negative terms take the largest remainders and the positive terms take the smallest remainders, there can be a lower bound for the sum. Is there any way to get a better approximation formula that may require us to know something more than the remainders of $kn$ mod $l$ are all distinct? $\endgroup$ Apr 28 at 3:12

You must log in to answer this question.

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