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, 2014 at 17:19
  • $\begingroup$ It is ok. Why do you say it is unexpectedly short? $\endgroup$
    – Crostul
    Sep 9, 2014 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, 2014 at 17:42

1 Answer 1

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, 2014 at 17:46
  • 1
    $\begingroup$ Floors & ceilings can be confusing. $\endgroup$
    – copper.hat
    Sep 9, 2014 at 17:51
  • 3
    $\begingroup$ (I was actually serious when I wrote the previous comment, it has nothing to do with alcohol consumption.) $\endgroup$
    – copper.hat
    Sep 9, 2014 at 17:59

You must log in to answer this question.

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