5
$\begingroup$

In this text the fractional part of a real $x$ shall be denoted $\{x\}$, such that $x = \lfloor x \rfloor + \{x\}$.

Theorem:

$$ \forall x \in \mathbb{R}_{\geq 0} \forall n \in \mathbb{N}_{\geq 1} : \left\lfloor x \right\rfloor \geq n \left\lfloor \frac{x}{n} \right\rfloor $$

Proof:

Let $n$ be a positive integer. Let $x$ be a nonnegative real number.

$$ x = n \frac{x}{n} = n \left( \left\lfloor \frac{x}{n} \right\rfloor + \left\{\frac{x}{n}\right\} \right) $$

Keeping in mind that the floor function is increasing:

$$ \lfloor x \rfloor = \left\lfloor n \left\lfloor \frac{x}{n} \right\rfloor + n \left\{\frac{x}{n}\right\} \right\rfloor \geq \left\lfloor n \left\lfloor \frac{x}{n} \right\rfloor \right\rfloor = n \left\lfloor \frac{x}{n} \right\rfloor $$

$$\square$$

Having just written it down it seems so clear (and unexpectedly short), but is this proof correct? What could be improved about it?

$\endgroup$
3
  • 2
    $\begingroup$ Yes, it is correct. $\endgroup$
    – Zarrax
    Sep 9 '14 at 17:19
  • $\begingroup$ It is ok. Why do you say it is unexpectedly short? $\endgroup$
    – Crostul
    Sep 9 '14 at 17:34
  • $\begingroup$ @Crostul I suppose it has something to do with the theorem holding true only for integer $n$, a constraint I did not notice earlier. I am very new to this. $\endgroup$
    – Homeward
    Sep 9 '14 at 17:42
8
$\begingroup$

A shorter proof would note that we always have $y \ge \lfloor y \rfloor$, hence ${x \over n} \ge \lfloor {x \over n} \rfloor$. Multiplying by $n$ gives $x \ge n\lfloor {x \over n} \rfloor$. Taking the floor of both sides gives the desired result (noting that the floor of an integer is the integer).

$\endgroup$
3
  • $\begingroup$ Thank you. Your last sentence, although noted in my proof, I had not realised until the end. $\endgroup$
    – Homeward
    Sep 9 '14 at 17:46
  • 1
    $\begingroup$ Floors & ceilings can be confusing. $\endgroup$
    – copper.hat
    Sep 9 '14 at 17:51
  • 2
    $\begingroup$ (I was actually serious when I wrote the previous comment, it has nothing to do with alcohol consumption.) $\endgroup$
    – copper.hat
    Sep 9 '14 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.