# Ceiling to Floor Function Conversion Proof

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

-
Think of it like this: if $n$ is an integer, and $3 < n$, then clearly $4 \le n$. Here, $(q-1)m < n$ so $(q-1)m+1 \le n$. – George V. Williams Jul 1 '13 at 17:46
Good answer, thank you! – nucleic Jul 1 '13 at 18:25
Why is it necessary to add that +1 tho? – nucleic Jul 1 '13 at 19:35

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

-
You're the man! – nucleic Jul 2 '13 at 0:25