I'm reading Concrete Mathematics. The problem is from Exercise 3.2 of this book.

The answer is pretty obvious

$$ \lfloor x + 0.5\rfloor, \text{if \{x\} = 0.5 then ceil should be considered}\\ \lceil x - 0.5 \rceil, \text{if \{x\} = 0.5 then floor should be considered} $$ where {x} = fractional part of x

The problem is I'm not able to prove the above equations. How to prove it ?

  • $\begingroup$ What is the question? I don't have the book. $\endgroup$ Sep 10 '17 at 8:49
  • $\begingroup$ how to prove the above two formulas ? $\endgroup$
    – Abhisek
    Sep 10 '17 at 8:50
  • $\begingroup$ I was puzzled for a moment. I guess that he means: "prove that these formula give you the nearest integer". $\endgroup$
    – badjohn
    Sep 10 '17 at 8:51
  • $\begingroup$ yes correct @badjohn $\endgroup$
    – Abhisek
    Sep 10 '17 at 8:52

Since $\lfloor y\rfloor \le y<\lfloor y\rfloor+1$ and there does not exist an integer $n$ with $\lfloor y\rfloor <n<\lfloor y\rfloor+1$, the only candidates for the nearest integer to $y$ are $\lfloor y\rfloor$ and $\lfloor y\rfloor+1$. The distances are $|y-\lfloor y\rfloor|=y-\lfloor y\rfloor =\{y\}$ and $|y-\lfloor y\rfloor-1|=1-y+\lfloor y\rfloor =1-\{y\}$, respectively. To find the nearest, we have to compare $\{y\}$ against $1-\{y\}$ or equivalently, $2\{y\}$ againts $1$. Thus

  • If $0\le \{y\}<\frac12$, then the nearest integer is $\lfloor y\rfloor$
  • If $\frac12 <\{y\}<1$, then the nearest integer is $\lfloor y\rfloor+1$
  • If $\{y\}=\frac12$, then both $\lfloor y\rfloor$ and $\lfloor y\rfloor+1$ are nearest integers.

Remains to show that these piecewise definitions coincide with $\lfloor y+\frac12\rfloor$ (the treatment of $\lceil y-\frac12\rceil$ is similar).

  • If $0\le\{y\}<\frac12$ then $y+\frac12<\lfloor y\rfloor +\frac12+\frac12=\lfloor y\rfloor +1$ and hence $\lfloor y+\frac12\rfloor <\lfloor y\rfloor +1$. Together with $\lfloor y+\frac12\rfloor \ge\lfloor y\rfloor$ we conclude that $\lfloor y+\frac12\rfloor = \lfloor y\rfloor$ as desired.
  • If $\frac12<\{y\}<1$ then $y+\frac12>\lfloor y\rfloor +\frac12+\frac12=\lfloor y\rfloor+1\in\Bbb Z$ and hence $\lfloor y+\frac12\rfloor \ge\lfloor y\rfloor +1$. Together with $\lfloor y+\frac12\rfloor\le \lfloor y+1\rfloor=\lfloor y\rfloor +1$, we conclude $\lfloor y+\frac12\rfloor =\lfloor y\rfloor +1$.
  • If $\{y\}=\frac12$, one readily verifies that $\lfloor y+\frac12\rfloor=\lfloor y\rfloor +1$

In summary, for all $y\in\Bbb R$, $\lfloor y+\frac12\rfloor$ is a nearest integer of $y$.

  • $\begingroup$ Very nice proof. I have just one question. Considering the fact that you know solution, You use different conditions (in this case 3) and arrive at single common expression (in this case $\lfloor y + \frac{1}{2} \rfloor$). Suppose you don't know what is the solution, how will you know what is the common single expression that you need to stop at, from all different conditions ? $\endgroup$
    – Abhisek
    Sep 10 '17 at 9:31

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.