# 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)$

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.

• Formulas from en.wikipedia.org/wiki/Floor_and_ceiling_functions can be helpful. Commented Feb 27, 2023 at 15:37
• Thanks for this initial post! Hadn't seen it before but it has lots of useful identities. Commented Feb 28, 2023 at 15:19

## 1 Answer

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{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}\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{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}\tag{6}\label{eq6A}

• That helps a lot, thanks! Commented Feb 28, 2023 at 15:18
• @Lambda You're welcome. FYI, I realized I didn't need to explicitly calculate and use $\sum_{k=1}^{m-1}\left\lfloor\frac{nk}{m}\right\rfloor$ since it just cancels out later. Thus, I've updated my answer accordingly, with it now being somewhat simpler & shorter than it was before. Commented Feb 28, 2023 at 20:53