6
$\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$
  • 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$
  • $\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.