Floor and Ceiling#
Contents#
Definition#
The floor and ceiling functions are defined for all real numbers.
For real numbers \(\alpha\) the floor function \(\lfloor \alpha \rfloor\) is the largest integer not exceeding \(\alpha\).
For real numbers \(\alpha\) the ceiling function \(\lceil \alpha \rceil\) is the smallest integer \(u\) s.t. \(a \le u\).
The fractional part of \(\alpha\) is the difference \(\alpha - \lfloor \alpha \rfloor\) and is denoted \(\{ \alpha \}\).
EXAMPLE
\( \begin{aligned} \lfloor \pi \rfloor &= 3 \\ \lceil \pi \rceil &= 4 \\ \lfloor \sqrt{2} \rfloor &= 1 \\ \lfloor -\sqrt{2} \rfloor &= -2 \\ \lceil -\sqrt{2} \rceil &= -1 \\ \end {aligned} \)
Properties#
1. \(\forall \alpha \in \mathbb{R} \quad 0 \le \alpha - \lfloor \alpha \rfloor \lt 1\)
2. \(\forall \alpha \in \mathbb{R}, k \in \mathbb{Z} \quad \lfloor \alpha + k \rfloor = \lfloor \alpha \rfloor + k\)
3. \(\forall \alpha \in \mathbb{R}, n \in \mathbb{N} \quad \lfloor \alpha / n \rfloor = \lfloor \lfloor \alpha \rfloor / n \rfloor\)
4. \(\forall \alpha, \beta \in \mathbb{R} \quad \lfloor \alpha \rfloor + \lfloor \beta \rfloor \le \lfloor \alpha + \beta \rfloor \le \lfloor \alpha \rfloor + \lfloor \beta \rfloor + 1\)
Proof by contradiction of property 1#
If \(\alpha - \lfloor \alpha \rfloor \lt 0\) then \(\alpha \lt \lfloor \alpha \rfloor\) which contradicts the definition. Thus \(\alpha - \lfloor \alpha \rfloor \ge 0 \iff \alpha \ge \lfloor \alpha \rfloor\).
If \(1 \le \alpha - \lfloor \alpha \rfloor\) then \(1 + \lfloor \alpha \rfloor \le \alpha\) which contradicts the definition. (“One more than the largest integer not exceeding \(\alpha\) does not exceed \(\alpha\).”) Thus \(1 \gt \alpha - \lfloor \alpha \rfloor \iff 1 + \lfloor \alpha \rfloor \gt \alpha \iff \lfloor \alpha \rfloor \gt \alpha - 1\).
This shows that \(\lfloor \alpha \rfloor\) is unique since \(\alpha \ge \lfloor \alpha \rfloor \gt \alpha - 1\).
\(\blacksquare\)
Proof of property 2#
Property 1 tells us that \(\alpha = \lfloor \alpha \rfloor + \theta\) for some \(\theta\) with \(0 \le \theta \lt 1\).
\( \begin{aligned} \alpha &= \lfloor \alpha \rfloor + \theta \\ \alpha \textcolor{yellow}{+ k} &= \lfloor \alpha \rfloor + \theta \textcolor{yellow}{+ k} \\ \theta &= \alpha + k - \lfloor \alpha \rfloor - k \\ \theta &= \alpha + k - (\lfloor \alpha \rfloor + k) \\ \end {aligned} \)
Since there is only one integer \(I\) with \(0 \le (\alpha + k) - I \lt 1\) and \(I = \lfloor \alpha + k \rfloor\) it must be the case that \(\lfloor \alpha + k \rfloor = \lfloor \alpha \rfloor + k\).
\(\blacksquare\)
Proof of property 3#
\( \begin{aligned} \theta &= \alpha / n - \lfloor \alpha / n \rfloor && \text{satisfies } 0 \le \theta \lt 1 \text{ according to property 1} \\ n \theta &= \alpha - n \lfloor \alpha / n \rfloor && \text{multiply by } n \\ \alpha &= n \lfloor \alpha / n \rfloor + n \theta && \text{rearrange terms} \\ \lfloor \alpha \rfloor &= \lfloor n \lfloor \alpha / n \rfloor + n \theta \rfloor && \text{apply the floor function, where } \lfloor n \lfloor \alpha / n \rfloor \in \mathbb{Z} \text{ and } n \theta \in \mathbb{R} \\ \lfloor \alpha \rfloor &= n \lfloor \alpha / n \rfloor + \lfloor n \theta \rfloor && \text{according to property 2} \\ \textcolor{lightgreen}{\lfloor \alpha \rfloor / n} &= \textcolor{green}{\lfloor \alpha / n \rfloor + \lfloor n \theta \rfloor / n} && \text{divide by } n \\ \end {aligned} \)
\( \begin{aligned} 0 &\le \theta &&\lt 1 \\ 0 &\le n\theta &&\lt n && \text{multiply by } n \\ 0 &\le \lfloor n\theta \rfloor &&\lt n && \text{apply the floor function} \\ 0 &\le \lfloor n\theta \rfloor / n &&\lt 1 && \text{divide by } n \\ \lfloor \alpha / n \rfloor &\le \textcolor{green}{\lfloor \alpha / n \rfloor + \lfloor n\theta \rfloor / n} &&\lt \lfloor \alpha / n \rfloor + 1 && \text{add } \lfloor \alpha / n \rfloor \\ \lfloor \alpha / n \rfloor &\le \textcolor{lightgreen}{\lfloor \alpha \rfloor / n} &&\lt \lfloor \alpha / n \rfloor + 1 \\ \lfloor \lfloor \alpha / n \rfloor \rfloor &= \lfloor \lfloor \alpha \rfloor / n \rfloor && && \text{apply the floor function} \\ \lfloor \alpha / n \rfloor &= \lfloor \lfloor \alpha \rfloor / n \rfloor \\ \end {aligned} \)
\(\blacksquare\)
Proof of property 4#
Let \(\alpha = \lfloor \alpha \rfloor + \theta\) and \(\beta = \lfloor \beta \rfloor + \phi\) where \(0 \le \theta, \phi \lt 1\).
\( \begin{aligned} \alpha + \beta &= \lfloor \alpha \rfloor + \lfloor \beta \rfloor + \theta + \phi \\ \lfloor \alpha + \beta \rfloor &= \lfloor \lfloor \alpha \rfloor + \lfloor \beta \rfloor + \theta + \phi \rfloor && \text{apply the floor function, where } \lfloor \alpha \rfloor + \lfloor \beta \rfloor \in \mathbb{Z} \text{ and } \theta + \phi \in \mathbb{R} \\ \lfloor \alpha + \beta \rfloor &= \lfloor \alpha \rfloor + \lfloor \beta \rfloor + \lfloor \theta + \phi \rfloor && \text{according to property 2} \\ \end {aligned} \)
\( \begin{aligned} 0 &\le \theta + \phi &&\lt 2 \\ 0 &\le \lfloor \theta + \phi \rfloor &&\le 1 && \text{apply the floor function} \\ \lfloor \alpha \rfloor + \lfloor \beta \rfloor &\le \lfloor \alpha \rfloor + \lfloor \beta \rfloor + \lfloor \theta + \phi \rfloor &&\le \lfloor \alpha \rfloor + \lfloor \beta \rfloor + 1 && \text{add } \lfloor \alpha \rfloor + \lfloor \beta \rfloor \\ \lfloor \alpha \rfloor + \lfloor \beta \rfloor &\le \lfloor \alpha + \beta \rfloor &&\le \lfloor \alpha \rfloor + \lfloor \beta \rfloor + 1 \\ \end {aligned} \)
\(\blacksquare\)
Acknowledgements#
[ h ] Vaughan, Robert. A Course of Elementary Number Theory.