4

Prove that $ \left\lfloor{\frac xn}\right\rfloor= \left\lfloor{\lfloor{x}\rfloor\over n}\right\rfloor$ where $n \ge 1, n \in \mathbb{N}$ and $\lfloor{.}\rfloor$ represents Greatest Integer $\mathbf{\le x}$ or floor function

I tried to prove it by writing $x = \lfloor{x}\rfloor + \{x\} $ where $ \{.\}$ represents Fractional Part function and $ 0 \le \{x\} < 1$ So we get,

$ \lfloor{\frac xn}\rfloor= \lfloor{{\lfloor x\rfloor\over n}+ {\{x\}\over n}}\rfloor \tag{1}$

Then I tried to use the property,

$\lfloor{x+y}\rfloor =\begin{cases} \lfloor x\rfloor + \lfloor y\rfloor& \text{if $0\le \{x\} + \{y\}$} < 1 \tag{2}\\ 1+ \lfloor x\rfloor + \lfloor y\rfloor & \text{if $1\le \{x\} + \{y\}$} < 2 \\ \end{cases} $

So if I can prove $(1)$ = first case of $(2) $ I’ll have ,

$ \lfloor{\frac xn}\rfloor= \lfloor{{\lfloor x\rfloor\over n}}\rfloor+ \lfloor{\{x\}\over n}\rfloor = \lfloor{\lfloor{x}\rfloor\over n}\rfloor$ as the second term will come out to be zero. However, I am unable to prove this.

Can someone help me out with this proof by showing me how $\mathbf(1)$= first case of $\mathbf (2)$ and proving the question using this method and also giving a clear proof using a simpler method

Hola
  • 155

3 Answers3

4

Simpler method, using only that :

if $m$ is an integer and $y$ is a real then $y \ge m \Longleftrightarrow \lfloor y \rfloor \ge m$.

\begin{align*} \big\lfloor \frac{x}{n}\big\rfloor &=\max\big\{k\in \mathbb{Z}\ |\ \frac{x}{n} \ge k\big\}=\max \big\{k\in\mathbb{Z}\ |\ x \ge nk\big\}\\ &=\max \big\{k\in\mathbb{Z}\ |\ \lfloor x\rfloor \ge nk\big\}=\max\big\{k\in\mathbb{Z}\ |\ \frac{\lfloor x\rfloor}{n}\ge k\big\} = \big\lfloor\frac{\lfloor x\rfloor}{n}\big\rfloor. \end{align*}

charmd
  • 6,050
  • 1
    Nice. Might be easier to read without all the $\max$ calls. For $k\in \mathbb Z: $ $$k\leq \frac{x}{n}\iff nk\leq x\iff nk\leq\lfloor x\rfloor \iff k\leq\frac{\lfloor x\rfloor}{n}$$ Your way of writing it, while correct, hides the simplicity of the argument. – Thomas Andrews Jul 18 '18 at 15:37
  • @Thomas Andrews the way you wrote it is indeed better, thanks – charmd Jul 18 '18 at 15:48
  • In the original answer can you explain how $k$ went from $k \in \mathbb{Z} $ to $k \in \mathbb{N} $ ? I know it doesn’t make a difference to the proof but I was curious to know. It should remain $ k \in \mathbb{Z} $ right ? – Hola Jul 19 '18 at 06:54
  • @Hola indeed, will correct that – charmd Jul 19 '18 at 09:06
2

The OP's proof method is a good one. It remains to calculate $$\left\{\frac{\lfloor x \rfloor}{n}\right\}$$ and $$\left\{\frac{\{x \}}{n}\right\}$$

Note that the first one is at most $\frac{n-1}{n}$, and the second is strictly less than $\frac{1}{n}$, hence their sum is strictly less than $1$.

More details, as requested:

Since $\lfloor x\rfloor$ is an integer, write it as $qn+r$, where $q,r$ are integers and $0\le r\le n-1$. This is the division algorithm. Now $\frac{\lfloor x \rfloor}{n}=\frac{qn+r}{n}=q+\frac{r}{n}$. This has fractional part $\frac{r}{n}$, which is at most $\frac{n-1}{n}$.

Now, $0\le \{x\}<1$, so $0\le \frac{\{x\}}{n}<\frac{1}{n}$. It is its own fractional part (since it's between $0$ and $1$), which is strictly less than $\frac{1}{n}$.

vadim123
  • 82,796
  • Thanks for answering. I’m sorry I didn’t understand. Can you please explain how first one is at most (n-1)/n and second is strictly less than 1/n? – Hola Jul 18 '18 at 14:52
  • 1
    {x}/n is strictly less than 1/n. What can I say about {{x}/n} ? And I can’t understand how first one is at most (n-1)/n – Hola Jul 18 '18 at 14:54
  • 2
    If $ 0 \le y < y$ then ${y} = y$ So ${\frac {{x}}n } =\frac {{x}}n < \frac 1n$. As for then first $[x]= k$ is an integer so $\frac kn = a + \frac bn$ for integers $a$ and $b$ and $b$ is at most $n - 1$. – fleablood Jul 18 '18 at 15:27
1

Consider by the archimedian principal there are a unique integers $k,m$ so that $kn \le kn + m\le x< kn + m + 1 \le (k+1)n$.

So $\frac {[x]}n = k + \frac mn$

So $\{\frac {[x]}n\} = \frac mn\le \frac {n-1}n$ and $\frac {\{x\}}n < \frac 1n$ so $\{\frac {\{x\}}n\} = \frac {\{x\}}n < \frac 1n$.

So $\{\frac {[x]}n\} + \{\frac {\{x\}}n\} = \frac mn + \frac {\{x\}}n < \frac {n-1}n + \frac 1n = 1$.

fleablood
  • 124,253