I am working on a proof to convert a ceiling of a fraction to a floor of a fraction. I found this:
\begin{aligned} q=\left\lceil \frac{n}{m} \right\rceil \;&\Leftrightarrow\; \frac{n}{m} \leq q < \frac{n}{m}+1 \;\Leftrightarrow\; n \leq q m < n+m \;\Leftrightarrow\; (q-1) m < n \leq q m \\ &\Leftrightarrow\; (q-1) m+1 \leq n \leq q m. \end{aligned}
Can anyone explain to me why we added the +1 on the last step to change the less than to a less than or equal to? What property do we use to do that? Can you also explain the intuition behind this? Thank you!
Here is my reference: http://blog.janmr.com/2009/09/useful-properties-of-the-floor-and-ceil-functions.html
For your conversion, you don’t really need (or even want) that last step. I would change it:
$$\begin{align*} q=\left\lceil\frac{n}m\right\rceil&\iff\frac{n}m\le q<\frac{n}m+1\\\\ &\iff n\le qm<n+m\\\\ &\iff (q-1)m<n\le qm\\\\ &\iff q-1<\frac{n}m\le q\;.\tag{1} \end{align*}$$
The inequality $(1)$ is almost the statement that $\left\lfloor\frac{n}m\right\rfloor=q-1$, but not quite:
$$\left\lfloor\frac{n}m\right\rfloor=q-1\iff q-1\le\frac{n}m<q\;.\tag{2}$$
If $(1)$ holds, then either
$$q-1<\frac{n}m<q\;,$$
in which case $(2)$ holds, and $\left\lfloor\frac{n}m\right\rfloor=q-1$, or $\frac{n}m=q$, in which case
$$\left\lfloor\frac{n}m\right\rfloor=\left\lceil\frac{n}m\right\rceil=\frac{n}m=q\;.$$
In other words, if $q=\left\lceil\frac{n}m\right\rceil$, then either $\frac{n}m=q$ is an integer already, or $\left\lfloor\frac{n}m\right\rfloor=q-1$.
To see why the step $(q-1)m<n\le qm\iff(q-1)m+1\le n\le qm$ is legitimate, note that the three numbers $(q-1)m$, $n$, and $qm$ are all integers. If $a$ and $b$ are integers, and $a<b$, then $b$ must be at least $a+1$, since there is no integer strictly between $a$ and $a+1$: $b\ge a+1$, or, equivalently, $a+1\le b$. Now let $a=(q-1)m$ and $b=n$, and you see that $$(q-1)m<n\le qm\implies(q-1)m+1\le n\le qm\;;$$ the other direction is trivial.
Note that in general it’s not true that $a<b\implies a+1\le b$; we can take this step here because we’re dealing with integers. Thus, in general the statement $a+1\le b\le c$ is a stronger statement than $a<b\le c$. By taking that last step from $(q-1)m<n\le qm$ to $(q-1)m+1\le n\le qm$, the author of that web page makes explicit the exact range of possible values of $n$: the smallest possibility is the integer $(q-1)m+1$ (and the largest is of course $qm$).