Floor of m+n-1 over n

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m, n \in \Z$ such that $n > 0$.

Then:

$\floor {\dfrac {m + n - 1} n} = \ceiling {\dfrac m n}$

The identity does not necessarily apply for $n < 0$.


Example

Let $n \in \Z$.

Then:

$\left \lfloor{\dfrac {n + 2 - \left \lfloor{n / 25}\right \rfloor} 3}\right \rfloor = \left \lfloor{\dfrac {8 n + 24} {25} }\right \rfloor$


Proof

First let $n > 0$ as stated.

Suppose $n \divides m$.

Then $m = k n$ for some $k \in \Z$.

It follows that:

$\floor {\dfrac {m + n - 1} n} = \floor {k + 1 - \dfrac 1 n} = k$

and:

$\ceiling {\dfrac m n} = k$


Now suppose $n \nmid m$.

Since $n > 0$, we have $m = k n + r$ for some $k \in\Z$ and $r \in \N$, $0 < r < n$.

Therefore:

$\floor {\dfrac {m + n - 1} n} = \floor {k + 1 + \dfrac {r - 1} n} = k + 1$

and:

$\ceiling {\dfrac m n} = k + 1$

$\Box$


Setting $m = 1, n = -2$ we have:

\(\displaystyle \floor {\dfrac {m + n - 1} n}\) \(=\) \(\displaystyle \floor {\dfrac {1 + \paren {-2} - 1} {\left({-2}\right)} }\)
\(\displaystyle \) \(=\) \(\displaystyle \ceiling 1\)
\(\displaystyle \) \(=\) \(\displaystyle 1\)
\(\displaystyle \) \(\ne\) \(\displaystyle 0\)
\(\displaystyle \) \(=\) \(\displaystyle \ceiling {\dfrac 1 {\paren {-2} } }\)
\(\displaystyle \) \(=\) \(\displaystyle \ceiling {\dfrac m n}\)

Thus, as stated, it is confirmed that the identity does not hold for $n < 0$.

It is noted that when $n = 0$ the expressions on either side are not defined.

$\blacksquare$


Sources