# Is this 'floor' proof correct.

• Jan 22nd 2010, 02:51 AM
Is this 'floor' proof correct.
For $n \in \mathbb{N}$ show that $\left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.

My proof...

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

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

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

So $\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 $\frac{l}{n} < 1$, $\frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}$

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

Then $\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 $0 \leq l \leq n-1$, $l + \delta < n$, hence $\frac{l + \delta}{n} < 1 => \left\lfloor \frac{l + \delta}{n} \right\rfloor= 0$.

So $\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 $x$ that $n$ divides would be 12, $l$ would be 1 and $\delta$ would be 0.86.

EDIT: I suppose this proof would also work for the case for $x < n$ actually.
• Jan 22nd 2010, 04:41 AM
tonio
Quote:

Originally Posted by Deadstar
For $n \in \mathbb{N}$ show that $\left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.

My proof...

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

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

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

So $\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 $\frac{l}{n} < 1$, $\frac{k}{n} + \left\lfloor \frac{l}{n} \right\rfloor = \frac{k}{n} + 0 = \frac{k}{n}$

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

Then $\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 $0 \leq l \leq n-1$, $l + \delta < n$, hence $\frac{l + \delta}{n} < 1 => \left\lfloor \frac{l + \delta}{n} \right\rfloor= 0$.

So $\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 $x$ that $n$ divides would be 12, $l$ would be 1 and $\delta$ would be 0.86.

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

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

1) $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}$ $\Longrightarrow \left[\frac{[x]}{n}\right]=\left[\frac{kn}{n}\right]=k=\left[\frac{x}{n}\right]$

2) $x this case's trivial, as you pointed out.

Tonio
• Jan 22nd 2010, 05:41 AM
Quote:

Originally Posted by tonio
1) $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 $x = kn + 0.a_1a_2$ part. Surely the $0.a_1a_2$ should start with any integer less or equal to n-1

For example. Take $\frac{12.345}{5}$, x=12.345, n=5. There is no $k \in \mathbb{N}$ such that $x = kn + 0.a_1a_2$, the $0$ in $0.a_1a_2$ would be a 2 would it not?
• Jan 22nd 2010, 07:21 AM
tonio
Quote:

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

For example. Take $\frac{12.345}{5}$, x=12.345, n=5. There is no $k \in \mathbb{N}$ such that $x = kn + 0.a_1a_2$, the $0$ in $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 $x=kn+a_0.a_1\ldots\,,\,k,\,a_i\in\mathbb{N}\,,\,\, 0\le a_0 , so

$\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 $a_0\,,\,a_0.a_1\ldots < n$

Tonio
• Jan 22nd 2010, 08:03 AM
Cheers.

I had a feeling my answer was messy but I think it's technically correct. Your way looks a lot better though.
• Jan 22nd 2010, 03:32 PM
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 $n$ is a factor of $x$, also meaning $x \in \mathbb{N}$, then $\left\lfloor\frac{x}{n}\right\rfloor = \frac{x}{n}$ and $x=\lfloor x \rfloor$.
2) For $0\leq y<1$, $\left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff$ $n$ is a factor of $x$.
3) Since $0\leq x-\lfloor x \rfloor < 1$, then $\left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$.
• Jan 23rd 2010, 11:04 AM
Quote:

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 $n$ is a factor of $x$, also meaning $x \in \mathbb{N}$, then $\left\lfloor\frac{x}{n}\right\rfloor = \frac{x}{n}$ and $x=\lfloor x \rfloor$.
2) For $0\leq y<1$, $\left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff$ $n$ is a factor of $x$.
3) Since $0\leq x-\lfloor x \rfloor < 1$, then $\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?
• Jan 23rd 2010, 01:23 PM
Andre
Quote:

Originally Posted by Deadstar
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: $x=kn$ and $x \neq kn$, as described below...

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

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

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

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

If formalized, could this be a reasonable approach to proving $\left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor$ for $x=kn$ and $x \neq kn$?
• Jan 23rd 2010, 03:14 PM
Plato
Quote:

Originally Posted by Andre
I'm not at all a mathematician
Therefore, $\left\lfloor\frac{x}{n}\right\rfloor > \left\lfloor\frac{x-y}{n}\right\rfloor \iff x=kn$. Where $x \neq kn$, $\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 $x=8.1,~y=0.8~\&~n=4$ but $\left\lfloor {\frac{x}{n}} \right\rfloor > \left\lfloor {\frac{{x - y}}{n}} \right\rfloor \,\& \,x \ne kn$
• Jan 23rd 2010, 04:35 PM
Andre
At least I proved something! Sorry for all the noise, guys. (Nod)

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