4
$\begingroup$

How can I prove that if $x$ and $y$ are positive then

$$\lfloor x\rfloor\lfloor y\rfloor\le\lfloor xy\rfloor$$

$\endgroup$
  • 2
    $\begingroup$ Do you mean $\lfloor x\rfloor \lfloor y\rfloor$? $\endgroup$ – Dan Oct 4 '13 at 9:24
  • 4
    $\begingroup$ $x \ge \lfloor x\rfloor$ and $y\ge \lfloor y\rfloor$ imply $xy \ge \lfloor x\rfloor \lfloor y\rfloor$. $\endgroup$ – njguliyev Oct 4 '13 at 9:25
  • $\begingroup$ @Dan yes, I edit it. $\endgroup$ – user95733 Oct 4 '13 at 9:27
12
$\begingroup$

First note that $f:\mathbb R\rightarrow \mathbb Z$ given by $f(x)=\lfloor x\rfloor$ is an increasing function that is the identity on the integers. Then note that for positive $x$ we have $0\leq f(x)\leq x$. With this we get $$ f(x)f(y)\leq xy $$ and applying the increasing function $f$ on both sides above noting that the left hand side is an integer we then get: $$ f(x)f(y)=f(f(x)f(y))\leq f(xy) $$ which proves the claim.

$\endgroup$
10
$\begingroup$

Assuming that you mean $\lfloor x \rfloor \lfloor \color{red}{y} \rfloor \le \lfloor xy \rfloor$, write

$$x := a + b, \quad y = c + d, \quad a,c \in \mathbb{N} \cup \{0\}, \quad b,d \in [0,1\rangle.$$

Then $\lfloor x \rfloor \lfloor y \rfloor = ab$ and

$$\lfloor xy \rfloor = \lfloor (a+b)(c+d) \rfloor = \dots$$

$\endgroup$
  • 1
    $\begingroup$ I would personally write $x\equiv\lfloor x \rfloor+b$ and $y\equiv \lfloor y \rfloor+d$ $\endgroup$ – Mobius Pizza Oct 4 '13 at 9:38
  • 1
    $\begingroup$ @MobiusPizza I would go for what njguliyev wrote in comments, but this seemed a bit easier to comprehend to anyone having a problem with stuff like this, as it avoids getting expressions like $\lfloor \lfloor x \rfloor + b \rfloor$, i.e., $\lfloor \cdot \rfloor$ inside $\lfloor \cdot \rfloor$. That kind of stuff tends to confuse readers. $\endgroup$ – Vedran Šego Oct 4 '13 at 9:59
5
$\begingroup$

HINT: For this you need only a little more than the fact that if $x\ge 0$, then $0\le\lfloor x\rfloor\le x$ and basic facts about manipulating inequalities. Specifically, you need to realize that if $z\in\Bbb R$, $n\in\Bbb Z$, and $n\le z$, then $n\le\lfloor z\rfloor$.

$\endgroup$
  • $\begingroup$ I am not sure I get the 'you only need'. Do you really mean that any $f:\mathbb R^+\rightarrow \mathbb R^+$ so that $f(x)\leq x$ will have $f(x)f(y)\leq f(xy)$? $\endgroup$ – String Oct 4 '13 at 9:31
  • $\begingroup$ @String: It was overstated; I must have been thinking that the righthand side was $xy$. I’ve fixed it now. $\endgroup$ – Brian M. Scott Oct 4 '13 at 9:39
  • $\begingroup$ @BrianMScott: Great! I was just wondering. $\endgroup$ – String Oct 4 '13 at 9:53
0
$\begingroup$

I am using the notation $\{x\}$ to mean the fractional part of $x$. $$ x = \lfloor x \rfloor + \{x\}, \;\; y = \lfloor y \rfloor + \{y\} \\ xy = \lfloor x\rfloor \lfloor y \rfloor + \lfloor x\rfloor \{y\} + \{x\}\lfloor y\rfloor + \{x\} \{y\} \\ \lfloor xy\rfloor=\lfloor x\rfloor \lfloor y\rfloor + \lfloor\lfloor x\rfloor\{y\}\rfloor + \lfloor\{x\}\lfloor y\rfloor\rfloor\\ \text{but } x\ge0,\;\;y\ge0\\ \lfloor\lfloor x\rfloor\{y\}\rfloor + \lfloor\{x\}\lfloor y\rfloor\rfloor\ge0\\ \therefore \lfloor xy\rfloor\ge\lfloor x\rfloor\lfloor y\rfloor$$

$\endgroup$
0
$\begingroup$

$ \newcommand{floor}[1]{\left\lfloor #1 \right\rfloor} $Here is how I would write down this proof, essentially the proof from njguliyev's comment.

For all real $\;x,y \ge 0\;$, \begin{align} & \floor x \times \floor y \;\le\; \floor{x \times y} \\ \equiv & \qquad \text{"basic property of $\;\floor{\cdot}\;$, using that the left hand side is integer"} \\ & \floor x \times \floor y \;\le\; x \times y \\ \Leftarrow & \qquad \text{"arithmetic: the simplest possible strengthening, using $\;x,y \ge 0\;$"} \\ & \floor x \le x \;\land\; \floor y \le y \\ \equiv & \qquad \text{"basic property of $\;\floor{\cdot}\;$, twice"} \\ & \text{true} \\ \end{align}

$\endgroup$
0
$\begingroup$

We can use here the fact that if $x$ and $y$ are positive real numbers, then $[x]\leq\ x$ and $[y]\leq\ y$. So we multiply the inequalities to obtain $[x][y]\leq\ xy$ which implies that $[x][y]\leq\ [xy]$ (by using a well known properties of the floor function) and this proves the result. (Q.E.D.)

Hope this really helps you! :-)

$\endgroup$

Your Answer

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