# Floor Function Proof

Let $m \in \mathbb{R}$ and $n \in \mathbb{N}$. Prove the following facts:

$\lfloor \hspace2mm\rfloor$ Means Floor function: And $\lfloor \lfloor m\rfloor/n\rfloor$ mean the floor of $m$ and then the floor of the floor $m$ divides $n$.

(i) $\lfloor m+n \rfloor = \lfloor m \rfloor+n$

(ii) $\lfloor \lfloor m \rfloor / n \rfloor = \lfloor m/n \rfloor$

(iii) $\lfloor m \rfloor + \lfloor m + 1/n \rfloor + \lfloor m + 2/n \rfloor + \ldots + \lfloor m + (n-1)/n \rfloor = \lfloor m n \rfloor$ (induction?)

Lemma: for $x = nθ$, where $θ = m−\lfloor m \rfloor$.

-

For all the problems, the main thing you need is to write $$x = \lfloor x \rfloor + \{x\}$$ where $\lfloor x \rfloor \in \mathbb{Z}$ and $\{x\} \in [0,1)$.

For instance, for the first one

1. $\lfloor m + n \rfloor = \lfloor \lfloor m \rfloor +\{m\} + n \rfloor = \lfloor \lfloor m \rfloor + n +\{m\} \rfloor = \lfloor m \rfloor + n$.
2. If $$\lfloor \lfloor m \rfloor/n \rfloor = a \in \mathbb{Z}$$ then we have that $$\lfloor m \rfloor/n = a + b$$ where $b \in \left \{0,\dfrac1n, \dfrac2n, \ldots, \dfrac{(n-1)}n \right\}$. Hence, $$\lfloor m \rfloor = an + bn \implies m = an + bn + c$$ where $c \in [0,1)$. Hence, $$m/n = a + b + \dfrac{c}n$$ Note that $b + \dfrac{c}n \in \left\{ \dfrac{c}n,\dfrac{c+1}n, \ldots, \dfrac{c+(n-1)}n\right\} \subseteq [0,1)$. Hence, $$\lfloor m/n \rfloor = a = \lfloor \lfloor m \rfloor/n \rfloor$$
-
The proof of (2) is not quite right, since $m \in R$, not $N$. – marty cohen Jul 1 '15 at 22:03

The first two are straightforward using the universal property of the floor function, viz. $$\rm k\le \lfloor r \rfloor \iff k\le r,\ \ \ for\ \ \ k\in \mathbb Z,\ r\in \mathbb R$$ Therefore for $\rm\:0 < n\in \mathbb Z,\ r\in \mathbb R,\$ $$\rm\begin{eqnarray} &\rm k &\le&\:\rm\ \lfloor \lfloor r \rfloor / n\rfloor \\ \iff& \rm k &\le&\ \ \rm \lfloor r \rfloor / n \\ \iff& \rm nk &\le&\ \ \rm \lfloor r \rfloor \\ \iff& \rm nk &\le&\ \ \rm r \\ \iff& \rm k &\le&\ \ \rm r/n \\ \iff& \rm k &\le&\ \ \rm \lfloor r/n \rfloor \\ \\ \Rightarrow\ \ \rm \lfloor \lfloor r\!\!&\rm \rfloor / n\rfloor\ &=&\rm\ \ \lfloor r/n\rfloor \end{eqnarray}$$

since, having equal predecessors, these integers are equal.

If you know a little category theory you can view this universal property of floor as a right adjoint to inclusion, e.g. see Arturo's answer here, or see most any textbook on category theory. But, of course, one need not know any category theory to understand the above proof. Indeed, I've had success explaining this (and similar universal-inspired proofs) to bright high-school students.

-

The floor function (also known as the entier function) is defined as having its value the largest integer which does not exceed its argument. When applied to any positive argument it represents the integer part of the argument obtained by suppressing the fractional part.

From this definition it is clear that for all positive real numbers x, y [x + y] > [x] + [y] since [x] and [y] are the integer parts of x and y. It's also obvious that equality is obtained when x and y are integers since they then have zero fractional parts.

let {x} = x - [x] and {y} = y - [y], so they are the decimal parts of x and y.

Then x + y = [x] + [y] + {x} + {y}

Case 1: {x} + {y} < 1 then {x + y} = {[x] + [y] +{x} + {y}} = {{x} + {y}} = {x} + {y} (we can remove from inside the {}s anything to the left of the decimal point!)

so [x+y] = x + y - {x + y} = x + y - {x} - {y} = [x] + [y]

Case 2: {x} + {y} >= 1 (but clearly must be <2) then {x + y} = {[x] + [y] + {x} + {y}} = {{x} + {y}} = {x} + {y} - 1

so [x + y] = x + y - {x + y} = x + y - {x} - {y} + 1 = [x] + [y] + 1

-

I hadn´t the joy of solving this. The beauty of this proof lies in a weird and simple relation between trigonometry, and number theory.

$$From\space trigonometry\space we\space have\quad \sin(nx)=2^{n-1}\space\prod_{k=0}^{n-1} \sin(\dfrac{\pi k }{n} + x) \quad and\space for\quad x\notin \mathbb Z\quad sgn(\sin(\pi x))=(-1)^{\lfloor x \rfloor}$$$$therefore$$ $$(-1)^{\lfloor nx \rfloor}=sgn(\sin(n\pi x))$$$$=sgn(2^{n-1}\space\prod_{k=0}^{n-1} \sin(\pi (\dfrac{ k }{n} + x))\space)$$$$=sgn(2^{n-1})\space sgn(\prod_{k=0}^{n-1} \sin(\pi (\dfrac{ k }{n} + x))\space)$$$$=\prod_{k=0}^{n-1} sgn( \sin(\pi (\dfrac{ k }{n} + x)\space)$$

$$=\prod_{k=0}^{n-1} (-1)^{\lfloor (\frac kn + x) \rfloor}$$ $$=(-1)^{\sum_{k=0}^{n-1} \lfloor (\frac kn + x) \rfloor}$$ and from both equation sides $${\lfloor nx \rfloor}={\sum_{k=0}^{n-1} \lfloor (\frac kn + x) \rfloor}$$

The trigonometric id is explained on other posts. You could demonstrate it by using the complex expression for sines.

-
I don't think so. Just because $(-1)^a = (-1)^b$, it does not follow that $a = b$. They could, for example, differ by 2. However, if you can show that $a$ and $b$ are integers that differ by less than 2, then they are equal. – marty cohen Jul 1 '15 at 22:08
True.... They differ by an even integer since the floor function returns integers. It seems less affordable to demonstrate that the difference is less than two than to demonstrate it by other means. – Saul Mendoza Jul 2 '15 at 21:27

$$Let\space m\space denote\space the \space integer\space part\space of \space x\in \mathbb R\space,\quad$$$$i.e. \space \space m\in \mathbb Z \mid m=\lfloor x \rfloor \quad and\quad \varepsilon =x-\lfloor x \rfloor,\space \varepsilon \in [0,1)$$$$Then \space we \space define\space k=\lfloor n\varepsilon \rfloor \in \left \{0,1, 2, \ldots, (n-1) \right\}$$$$so\space that\space \lfloor nx \rfloor=\lfloor n(m + \varepsilon) \rfloor=nm + \lfloor n \varepsilon \rfloor=nm + k$$$$on \space the \space other \space hand \quad \sum_{j=0}^{n-1} \lfloor x +(\frac jn) \rfloor={\sum_{j=0}^{n-1} \lfloor (m + \varepsilon) +(\frac jn) \rfloor}={\sum_{j=0}^{n-1} m + \lfloor \varepsilon +(\frac jn) \rfloor}={ nm + \sum_{j=0}^{n-1}\lfloor \varepsilon +(\frac jn) \rfloor}$$ $$but \quad {\sum_{j=0}^{n-1}\lfloor \varepsilon +(\frac jn) \rfloor}={\sum_{j=0}^{n-1}\lfloor\frac{n\varepsilon + j}{n} \rfloor}={\sum_{j=0}^{n-1}\lfloor\frac{\lfloor n\varepsilon + j\rfloor}{n} \rfloor}={\sum_{j=0}^{n-1}\lfloor\frac{\lfloor n\varepsilon\rfloor + j}{n} \rfloor}={\sum_{j=0}^{n-1}\lfloor\frac{k + j}{n} \rfloor}={\sum_{j=0}^{n-k-1}\lfloor\frac{k + j}{n} \rfloor +\sum_{j=n-k}^{n-1}\lfloor\frac{k + j}{n} \rfloor}={\sum_{j=n-k}^{n-1}\lfloor\frac{k + j}{n} \rfloor}={\sum_{j=n-k}^{n-1}(1)}=k$$ $$and\space consequently\quad \lfloor nx \rfloor=nm + k=\sum_{j=0}^{n-1} \lfloor x +(\frac jn) \rfloor$$

-

The number of positive integers less than or equal to ($x$) the (n) are divisible. Is equal to =$\left[\frac xn\right]$

The number of positive integers less than or equal to ($[x]$) the (n) are divisible. Is equal to =$\left[\frac {[x]}n\right]$

So should these two values are equal.

-