# Is this proof of $\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil$ correct?

I've been practicing proving things about floor and ceiling functions, so I thought I'd try to prove this well-known identity: $$\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil$$ for all $$n,m \in \mathbb{Z}$$, $$m>0$$.

This is what I came up with. Is my proof correct?

Proof:

[see edit below]

Case 1: $$m=1$$ $$\left\lfloor \frac{n}{1} \right\rfloor = \lfloor n \rfloor = n$$ $$\left\lceil \frac{n-1+1}{1} \right\rceil = \lceil n \rceil = n$$

Case 2: $$m>1$$

If $$\frac{n}{m}$$ is an integer, then

$$\left\lceil \frac{n-m+1}{m} \right\rceil = \left\lceil \frac{n}{m} -1 + \frac{1}{m}\right\rceil = \frac{n}{m} -1 + \left\lceil \frac{1}{m} \right\rceil = \frac{n}{m} -1 + 1 = \frac{n}{m} = \left\lfloor \frac{n}{m} \right\rfloor$$

If $$\frac{n}{m}$$ is NOT an integer, then

$$\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n}{m} \right\rceil - 1 = \left\lceil \frac{n}{m} + \frac{1}{m} \right\rceil - 1 = \left\lceil \frac{n}{m} + \frac{1}{m} -1 \right\rceil = \left\lceil \frac{n-m+1}{m} \right\rceil$$

$$\blacksquare$$

If it's correct but you know a simpler/better way to prove it, please include that in your answer. Thank you.

EDIT: As pointed out by user peterwhy, "Case 1: $$m=1$$" is simply a special case of "$$\frac{n}{m}$$ is an integer" and therefore is not needed; hence I have grayed it out, and we don't need to separate the $$m=1$$ and $$m>1$$ cases anymore.

• It looks right to me. Sep 12, 2022 at 18:21
• The $m=1$ case is also a specific case of the "$\frac nm$ is an integer" case. Sep 12, 2022 at 18:35
• @peterwhy good catch; no need for Case 1 then. Is there a way to prove it without distinguishing the integer case?
– SNN
Sep 12, 2022 at 20:36

Your proof looks okay (although the second equality in the $$n/m$$ not being integer might need some clarification). Notice that this identity can be proven essentially the same way as Prove that $\left\lceil \frac{n}{m} \right\rceil =\left \lfloor \frac{n+m-1}{m} \right\rfloor$ . Here is one variant.

By division with remainder, we can write $$n=\lfloor \frac{n}{m} \rfloor m+(n \bmod m)$$. Adding $$-m+1$$ to both sides and dividing by $$m$$ we get $$\frac{n-m+1}{m}=\Big\lfloor \frac{n}{m} \Big\rfloor +\frac{(n \bmod m)-m+1}{m}.\tag{*}$$ Since $$0 \leq n \bmod m \leq m-1$$, we have $$-m+1 \leq (n \bmod m)-m+1\leq 0$$. So the rightmost fraction in $$(*)$$ (denote $$x$$) satisfies $$-1<-1+\frac{1}{m}\leq x \leq 0$$. Hence applying the ceiling function (and using that $$\Big\lfloor \frac{n}{m} \Big\rfloor$$ is an integer), we get $$\Big\lceil \frac{n-m+1}{m}\Big\rceil =\Big\lfloor \frac{n}{m} \Big\rfloor +\Big\lceil\frac{(n \bmod m)-m+1}{m}\Big\rceil=\Big\lfloor \frac{n}{m} \Big\rfloor.$$

Note. Alternatively, if you already know the dual statement $$\left\lceil \frac{n}{m} \right\rceil =\left \lfloor \frac{n+m-1}{m} \right\rfloor$$, you can just use $$\lfloor -x \rfloor=-\lceil x \rceil$$ few times: $$\left\lfloor \frac{n}{m} \right\rfloor = -\Big\lceil \frac{-n}{m} \Big\rceil = - \left \lfloor \frac{-n+m-1}{m} \right\rfloor =-\Big(-\Big\lceil \frac{n-m+1}{m}\Big\rceil\Big)=\Big\lceil \frac{n-m+1}{m}\Big\rceil$$

• Also, in my proof, would it be sufficient clarification to say that assuming $n/m$ is non-integer, no integers exist strictly between $n/m$ and $n/m + 1/m$ and I'd justify it like so: assume toward a contradiction that there exists an integer $q$ between those two values. Then $n/m < q < n/m + 1/m$ implies $n < qm < n + 1$ but obviously since $n$ and $n+1$ are consecutive then $qm$ must be non-integer, which is a contradiction. Therefore no integers exist in that range, thus the ceiling of both expressions are equal. Is this correct and sufficient?
– SNN
Sep 14, 2022 at 15:38
– Sil
Sep 14, 2022 at 15:42

As in your previous question on floor and ceiling, I am finding the interval of both sides with inequalities.

Both sides are defined and are integers. They are respectively within these intervals:

$$\begin{array}{rrcl} \text{LHS:}&\dfrac nm-1 <&\left\lfloor\dfrac nm\right\rfloor&\le \dfrac nm\\\hline \text{RHS:}&\dfrac{n-m+1}{m}\le& \left\lceil\dfrac{n-m+1}{m}\right\rceil &< \dfrac{n-m+1}{m}+1\\ \iff&\dfrac{n+1}{m}-1\le& \left\lceil\dfrac{n-m+1}{m}\right\rceil &< \dfrac{n+1}{m}\\ \end{array}$$

The $$4$$ endpoints are in this order:

$$\frac nm-1 < \frac{n+1}m-1 \le \frac nm < \frac{n+1}m$$

There are no possible integers strictly between $$\dfrac nm-1 < \dfrac{n+1}m-1$$, and none strictly between $$\dfrac nm < \dfrac{n+1}m$$. Then both LHS and RHS can only be the one integer within the overlapping interval:

$$\frac{n+1}m-1 \le (\text{Both LHS and RHS})\le \frac nm$$

(BTW in the question, if $$\frac nm$$ is not an integer, then $$\left\lceil\frac nm\right\rceil = \left\lceil\frac nm + \frac 1m\right\rceil$$. While intuitive, no integer exists strictly between $$\frac nm < \frac{n+1}m$$ is how I would explain it to myself)

• Thank you for the alternate explanation at the end, I like that better and it's easy to prove rigorously.
– SNN
Sep 14, 2022 at 16:06

Another succinct proof is

$$\left\lfloor\frac nm\right\rfloor = \left\lfloor\frac{n + \frac12}m\right\rfloor = \left\lceil\frac{n - m + \frac12}m\right\rceil = \left\lceil\frac{n - m + 1}m\right\rceil,$$

since $$\frac{n + \frac12}m$$ and $$\frac{n - m + \frac12}m$$ are always non-integers with a difference of $$1$$.

• clever idea, however i don't think it's obvious that the first expression is equal to the second. it is intuitive, but it doesn't feel rigorous enough. how would you justify it in a sentence? one could prove it as follows, but i'm asking for something more concise: assume there is an integer $q$ strictly between $\frac{n}{m}$ and $\frac{n + \frac{1}{2}}{m}$ so we have $\frac{n}{m} < q < \frac{n + \frac{1}{2}}{m}$, which implies $n < mq < n + \frac{1}{2}$, which obviously says that $mq$ is non-integer, which is a contradiction; hence no integers exist strictly between those two expressions
– SNN
Sep 16, 2022 at 3:30
• @SNN The next integer after $\frac nm$ must be at least $\frac1m$ away, but we only moved by $\frac1{2m}$. (If you were to ask “why?”, the answer might be something like what you wrote, though your upper bound should be $≤$. But one can always continue answering “why?” until one has reached the axioms of set theory or beyond and written a thousand-page book. “Rigorous” doesn’t mean that you’ve written out every detail—it just means it’s clear how you could.) Sep 16, 2022 at 3:52
• that's reasonable, thank you
– SNN
Sep 16, 2022 at 12:57