# Thread: Is this 'floor' proof correct.

1. ## Is this 'floor' proof correct.

For $\displaystyle n \in \mathbb{N}$ show that $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.

My proof...

If $\displaystyle n > x$ both sides will be 0 so we will deal with the case when $\displaystyle n <= x$.

Let $\displaystyle k \neq 0$ be the largest integer smaller than $\displaystyle x$ such that $\displaystyle n | k$.

Then we have $\displaystyle \lfloor x \rfloor = k + l$ where $\displaystyle l \in \mathbb{N}$ and $\displaystyle 0 \leq l \leq n-1$.

So $\displaystyle \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor = \left\lfloor \frac{k + l}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor$ and since $\displaystyle \frac{l}{n} < 1$, $\displaystyle \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}$

Now let $\displaystyle x = \lfloor x \rfloor + \delta$ where $\displaystyle 0 \leq \delta < 1$.

Then $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{k+l}{n} + \frac{\delta}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor$.

And since $\displaystyle 0 \leq l \leq n-1$, $\displaystyle l + \delta < n$, hence $\displaystyle \frac{l + \delta}{n} < 1 => \left\lfloor \frac{l + \delta}{n} \right\rfloor= 0$.

So $\displaystyle \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}$. Hence the two are equal.

I hope I've written this out right. To explain if it looks wrong... Imagine, 13.86/4. Then the largest integer smaller than $\displaystyle x$ that $\displaystyle n$ divides would be 12, $\displaystyle l$ would be 1 and $\displaystyle \delta$ would be 0.86.

EDIT: I suppose this proof would also work for the case for $\displaystyle x < n$ actually.

For $\displaystyle n \in \mathbb{N}$ show that $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.

My proof...

If $\displaystyle n > x$ both sides will be 0 so we will deal with the case when $\displaystyle n <= x$.

Let $\displaystyle k \neq 0$ be the largest integer smaller than $\displaystyle x$ such that $\displaystyle n | k$.

Then we have $\displaystyle \lfloor x \rfloor = k + l$ where $\displaystyle l \in \mathbb{N}$ and $\displaystyle 0 \leq l \leq n-1$.

So $\displaystyle \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor = \left\lfloor \frac{k + l}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor$ and since $\displaystyle \frac{l}{n} < 1$, $\displaystyle \frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}$

Now let $\displaystyle x = \lfloor x \rfloor + \delta$ where $\displaystyle 0 \leq \delta < 1$.

Then $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{k+l}{n} + \frac{\delta}{n} \right\rfloor = \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor$.

And since $\displaystyle 0 \leq l \leq n-1$, $\displaystyle l + \delta < n$, hence $\displaystyle \frac{l + \delta}{n} < 1 => \left\lfloor \frac{l + \delta}{n} \right\rfloor= 0$.

So $\displaystyle \frac{k}{n} + \left\lfloor \frac{l + \delta}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}$. Hence the two are equal.

I hope I've written this out right. To explain if it looks wrong... Imagine, 13.86/4. Then the largest integer smaller than $\displaystyle x$ that $\displaystyle n$ divides would be 12, $\displaystyle l$ would be 1 and $\displaystyle \delta$ would be 0.86.

EDIT: I suppose this proof would also work for the case for $\displaystyle x < n$ actually.

This seems to be way too messy. I propose the following:

1) $\displaystyle x\geq n\Longrightarrow x=kn+0.a_1a_2\ldots\,,\,\,k\,,\,a_i\in\mathbb{N}\c up\{0\}\,,\,\,thus\,\,\,\frac{x}{n}=k+\frac{0.a_1\ ldots}{n}$ $\displaystyle \Longrightarrow \left[\frac{[x]}{n}\right]=\left[\frac{kn}{n}\right]=k=\left[\frac{x}{n}\right]$

2) $\displaystyle x<n\Longrightarrow$ this case's trivial, as you pointed out.

Tonio

3. Originally Posted by tonio
1) $\displaystyle x\geq n\Longrightarrow x=kn+0.a_1a_2\ldots\,,\,\,k\,,\,a_i\in\mathbb{N}\c up\{0\}\,,\,\,thus\,\,\,\frac{x}{n}=k+\frac{0.a_1\ ldots}{n}$
I don't think that's quite right though...
Specifically the $\displaystyle x = kn + 0.a_1a_2$ part. Surely the $\displaystyle 0.a_1a_2$ should start with any integer less or equal to n-1

For example. Take $\displaystyle \frac{12.345}{5}$, x=12.345, n=5. There is no $\displaystyle k \in \mathbb{N}$ such that $\displaystyle x = kn + 0.a_1a_2$, the $\displaystyle 0$ in $\displaystyle 0.a_1a_2$ would be a 2 would it not?

I don't think that's quite right though...
Specifically the $\displaystyle x = kn + 0.a_1a_2$ part. Surely the $\displaystyle 0.a_1a_2$ should start with any integer less or equal to n-1

For example. Take $\displaystyle \frac{12.345}{5}$, x=12.345, n=5. There is no $\displaystyle k \in \mathbb{N}$ such that $\displaystyle x = kn + 0.a_1a_2$, the $\displaystyle 0$ in $\displaystyle 0.a_1a_2$ would be a 2 would it not?

You are, of course, right: but making that correction, mutandis-mutandis, the proof stands, since then $\displaystyle x=kn+a_0.a_1\ldots\,,\,k,\,a_i\in\mathbb{N}\,,\,\, 0\le a_0<n$ , so

$\displaystyle \left[\frac{x}{n}\right]=\left[k+\frac{a_0.a_1\ldots}{n}\right]=k=\left[k+\frac{a_0}{n}\right]=\left[\frac{kn+a_0}{n}\right]=\left[\frac{[x]}{n}\right]$ , since both $\displaystyle a_0\,,\,a_0.a_1\ldots < n$

Tonio

5. Cheers.

I had a feeling my answer was messy but I think it's technically correct. Your way looks a lot better though.

6. I'm admittedly way out of my league here, especially when constructing proofs, but why is all that rigor necessary?

1) It seems self-evident that where $\displaystyle n$ is a factor of $\displaystyle x$, also meaning $\displaystyle x \in \mathbb{N}$, then $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor = \frac{x}{n}$ and $\displaystyle x=\lfloor x \rfloor$.
2) For $\displaystyle 0\leq y<1$, $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff$ $\displaystyle n$ is a factor of $\displaystyle x$.
3) Since $\displaystyle 0\leq x-\lfloor x \rfloor < 1$, then $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.

7. Originally Posted by Andre
I'm admittedly way out of my league here, especially when constructing proofs, but why is all that rigor necessary?

1) It seems self-evident that where $\displaystyle n$ is a factor of $\displaystyle x$, also meaning $\displaystyle x \in \mathbb{N}$, then $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor = \frac{x}{n}$ and $\displaystyle x=\lfloor x \rfloor$.
2) For $\displaystyle 0\leq y<1$, $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff$ $\displaystyle n$ is a factor of $\displaystyle x$.
3) Since $\displaystyle 0\leq x-\lfloor x \rfloor < 1$, then $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.
Maybe its just me but I don't follow this at all. Can you explain it more?

Maybe its just me but I don't follow this at all. Can you explain it more?
Sorry, I'm not at all a mathematician, so I'm not certain how to express this properly, let alone elegantly. It seems to me that it should be satisfactory to prove it for two simple and mutually-exclusive cases: $\displaystyle x=kn$ and $\displaystyle x \neq kn$, as described below...

Let $\displaystyle n,k \in \mathbb{N}$. Where $\displaystyle x=kn$, $\displaystyle x$ is an integer, therefore $\displaystyle x=\lfloor x \rfloor$ and $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.

Let $\displaystyle y\geq 0$ and $\displaystyle y<1$. This means $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor \geq \left\lfloor\frac{x-y}{n}\right\rfloor$. In other words, because $\displaystyle y\geq 0$, $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor$ can not be less than $\displaystyle \left\lfloor\frac{x-y}{n}\right\rfloor$.

$\displaystyle \frac{x}{n}$ is an integer only when $\displaystyle x=kn$. Therefore, $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff x=kn$. Where $\displaystyle x \neq kn$, $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor = \left\lfloor\frac{x-y}{n}\right\rfloor$.

$\displaystyle y$ represents $\displaystyle x-\lfloor x \rfloor$, so $\displaystyle \lfloor x \rfloor = x-y$.

If formalized, could this be a reasonable approach to proving $\displaystyle \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$ for $\displaystyle x=kn$ and $\displaystyle x \neq kn$?

9. Originally Posted by Andre
I'm not at all a mathematician
Therefore, $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff x=kn$. Where $\displaystyle x \neq kn$, $\displaystyle \left\lfloor\frac{x}{n}\right\rfloor = \left\lfloor\frac{x-y}{n}\right\rfloor$.
Well you have proven your first point.
That statement is false.
Let $\displaystyle x=8.1,~y=0.8~\&~n=4$ but $\displaystyle \left\lfloor {\frac{x}{n}} \right\rfloor > \left\lfloor {\frac{{x - y}}{n}} \right\rfloor \,\& \,x \ne kn$

10. At least I proved something! Sorry for all the noise, guys.

I see my error, thanks. I believe for my "if and only if" statement to work, $\displaystyle y$ must not be greater than $\displaystyle x-\lfloor x \rfloor$, but that simply leads to a restatement of the original problem.