Simplifying floor function summation $\sum^m_{k=0} \left(\left\lfloor{\frac{n}{m}k}\right\rfloor-\left\lceil{\frac{n}{m}(k-1)}\right\rceil\right)$

Question

Is there a way this summation can be simplified/cast in a more revelatory form (non-summation representation, single-term only, etc.)? $$\sum^m_{k=0} \left(\left\lfloor{\frac{n}{m}k}\right\rfloor-\left\lceil{\frac{n}{m}(k-1)}\right\rceil\right)$$

where $m$ and $n$ are natural numbers. I've tried converting the ceiling function to a floor function, but that didn't seem to make the expression any simpler. I know that identities such as $⌊nx⌋=\sum^{n-1}_{k=0}⌊x+\frac{k}{n}⌋$ greatly simplify floor-summations, and was wondering if a similar reduction could be performed here.

Answer 1

First, split your summation of the $2$ terms into $2$ separate summations, i.e.,

$$\sum_{k=0}^m\left(\left\lfloor\frac{n}{m}k\right\rfloor - \left\lceil\frac{n}{m}(k-1)\right\rceil\right) = \sum_{k=0}^m\left\lfloor\frac{nk}{m}\right\rfloor - \sum_{k=0}^m\left\lceil\frac{n(k-1)}{m}\right\rceil \tag{1}\label{eq1A}$$

As suggested in zkutch's comment, we can use several formulas in Wikipedia's Floor and ceiling functions article. First, though, define

$$d = \gcd(m,n), \; \; m = dm_1, \; \; n = dn_1, \; \; \gcd(m_1,n_1) = 1 \tag{2}\label{eq2A}$$

For the first term on the right in \eqref{eq1A}, we have

$$\sum_{k=0}^m\left\lfloor\frac{nk}{m}\right\rfloor = 0 + \sum_{k=1}^{m-1}\left\lfloor\frac{nk}{m}\right\rfloor + n \tag{3}\label{eq3A}$$

For \eqref{eq1A}'s second term on the RHS, using that $\lceil -x \rceil = -\lfloor x \rfloor$, we get

$$\begin{equation}\begin{aligned} \sum_{k=0}^m\left\lceil\frac{n(k-1)}{m}\right\rceil & = \left\lceil-\frac{n}{m}\right\rceil + 0 + \sum_{k=2}^m\left\lceil\frac{n(k-1)}{m}\right\rceil \\ & = -\left\lfloor\frac{n}{m}\right\rfloor + \sum_{k=1}^{m-1}\left\lceil\frac{nk}{m}\right\rceil \end{aligned}\end{equation}\tag{4}\label{eq4A}$$

Using that $\lceil x \rceil = \lfloor x \rfloor + r$, where $r = 0$ if $x$ is an integer, and $r = 1$ otherwise. Using \eqref{eq2A}, we have $\frac{nk}{m} = \frac{dn_{1}k}{dm_{1}} = \frac{n_{1}k}{m_{1}}$. Since $\gcd(m_1,n_1) = 1$, this is an integer only when $k$ is an integral multiple of $m_1$, i.e., $k = m_1, 2m_1, \ldots, (d-1)m_1$. This comprises $d-1$ values among the $m-1$ values being summed. We therefore have

$$\sum_{k=1}^{m-1}\left\lceil\frac{nk}{m}\right\rceil = \sum_{k=1}^{m-1}\left\lfloor\frac{nk}{m}\right\rfloor + (m - 1) - (d - 1) \tag{5}\label{eq5A}$$

Using \eqref{eq5A} in \eqref{eq4A}, with that result along with \eqref{eq3A} in \eqref{eq1A}, gives

$$\begin{equation}\begin{aligned} & \sum_{k=0}^m\left(\left\lfloor\frac{n}{m}k\right\rfloor - \left\lceil\frac{n}{m}(k-1)\right\rceil\right) \\ & = \left(\sum_{k=1}^{m-1}\left\lfloor\frac{nk}{m}\right\rfloor + n\right) - \left(-\left\lfloor\frac{n}{m}\right\rfloor + \sum_{k=1}^{m-1}\left\lfloor\frac{nk}{m}\right\rfloor + m - d\right) \\ & = n - m + \gcd(m,n) + \left\lfloor\frac{n}{m}\right\rfloor \end{aligned}\end{equation}\tag{6}\label{eq6A}$$