0
$\begingroup$

Prove that if $n \in \mathbb{Z^+} $

$$\left[\frac{\left[x\right]}{n}\right]=\left[\frac{x}{n}\right]$$

Proof is Trivial when $x \in \mathbb{Z}$.

When $x \notin \mathbb{Z} $ Let $x=p+f$ where $p \in \mathbb{Z}$ and $0 \lt f \lt 1$

Now we have LHS as $$\left[ \frac{p}{n}\right]$$

Let $p \lt n$

If we take number line we have $$p \lt p+f \lt p+1 \le n$$

Hence $$p+f \lt n$$

But now how can i conclude $$\left[ \frac{p}{n}\right]=\left[ \frac{p+f}{n}\right]$$

$\endgroup$
2
  • 1
    $\begingroup$ How do you get $p+1\leq n$? $\endgroup$
    – Servaes
    Commented Jan 5, 2018 at 17:13
  • $\begingroup$ From "Let $p < n$"? $\endgroup$ Commented Jan 5, 2018 at 17:16

2 Answers 2

4
$\begingroup$

Let $x=p+f$ where $p \in \mathbb{Z}$ and $0 \lt f \lt 1$

Let that be $0 \color{red}{\le} f \lt 1$ in general. Next, let $p = k \cdot n + r$ with $k, r \in \mathbb{Z}$ and $0 \le r \le n-1\,$ by Euclidean division, so that $\,x=k \cdot n + r + f\,$. Then, using that $0 \le r \le n-1$ and $0 \le r+f \lt n$:

  • $\displaystyle\left\lfloor\frac{\left\lfloor x\right\rfloor}{n}\right\rfloor=\left\lfloor\frac{k \cdot n + r}{n}\right\rfloor=\left\lfloor k+\frac{r}{n}\right\rfloor = k$

  • $\displaystyle\left\lfloor\frac{x}{n}\right\rfloor=\left\lfloor\frac{k \cdot n + r+f}{n}\right\rfloor=\left\lfloor k+\frac{r+f}{n}\right\rfloor = k$

$\endgroup$
0
2
$\begingroup$

By archemenian principal there is a unique integer $m$ so that

$mn \le x < (m+1) n$

And,, likewise, there is a unique integer $a$ so that $a \le x < a + 1$.

So $mn\le a \le x < a+1 \le (m+1)n$

And $m \le \frac an \le \frac xn < \frac an + \frac 1 n \le m+1$

From the above it is clear $[x] = a$, $[\frac xn] = m$ and $[\frac an]=[\frac {[x]} n] = m$.

The only real issue I elided over is assuming $mn\le a$ and that $a+1 \le (m+1)n$. Which... should be obvious. $a = \max \{z\in \mathbb Z|z \le x\}$ by definition, and $mn \in \{z\in \mathbb Z|z \le x\}$ so $mn \le a$. And $a + 1 = \min\{z\in \mathbb Z|z > x\}$ by definition and $(m+1)n \in \{z\in \mathbb Z|z > x\}$ so $a+1 \le (m+1)n$.

==== old and hard to read =====

Let $x = a + f$ where $a \in \mathbb Z$ and $0 \le f < 1$.

ANd let $a = m*n + r$ where $r, m\in \mathbb Z$ and $0 \le r < n$.

By the archimedian principal we can make such statements for unique $m,r,a,f$.

$\frac xn = \frac an + \frac fn < \frac an + \frac 1n$.

And and $m\le \frac an = m + \frac rn < m+1$ we have $[\frac an] = m$ and

$m \le \frac an < m + 1$ then $\frac {a+1}n \le m+ 1$ and $\frac an + \frac fn < m+1$. And $m\le \frac an + \frac fn = \frac xn < m+1$

So $[\frac xn ] = m$.

And $[\frac an] = m$

And $[x] = a$.

So that's it.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .