TAOCP 1.2.4 Exercise 4

Exercise 4. ▶ [M10] Using the previous exercise, prove that $\lfloor -x \rfloor = -\lceil x \rceil$.

Verified: yes
Solve time: 3m10s

Let $n=\lceil x\rceil$. By the defining property of the ceiling function, $n$ is the least integer greater than or equal to $x$. Equivalently,

$$ n-1 < x \le n. $$

Multiply every part of this inequality by $-1$. Since multiplication by a negative number reverses the inequalities, we obtain

$$ -(n-1) > -x \ge -n. $$

Since $-(n-1)=-n+1$, this becomes

$$ -n+1 > -x \ge -n. $$

Rewriting in the standard order gives

$$ -n \le -x < -n+1. $$

By the characterization of the floor function,

$$ \lfloor y\rfloor = m \quad\Longleftrightarrow\quad m \le y < m+1. $$

Taking $y=-x$ and $m=-n$, the inequality

$$ -n \le -x < -n+1 $$

shows that

$$ \lfloor -x\rfloor = -n. $$

Since $n=\lceil x\rceil$, it follows that

$$ \boxed{\lfloor -x\rfloor = -\lceil x\rceil}. $$

$\square$