Sum of Ceilings Not Less Than Ceiling of Sums

Theorem

Let $\left \lceil {x} \right \rceil$ be the ceiling function.

Then:

$\left \lceil {x} \right \rceil + \left \lceil {y} \right \rceil \ge \left \lceil {x + y} \right \rceil$

The equality holds:

$\left \lceil {x} \right \rceil + \left \lceil {y} \right \rceil = \left \lceil {x + y} \right \rceil$

iff either:

$x \in \Z$ or $y \in \Z$

or:

$x \,\bmod\, 1 + y \,\bmod\, 1 > 1$

where $x \,\bmod\, 1$ denotes the modulo operation.

Proof

From the definition of the modulo operation, we have that:

$x = \left \lfloor {x}\right \rfloor + \left({x \, \bmod \, 1}\right)$

from which we obtain:

$x = \left \lceil {x}\right \rceil - \left[{x \notin \Z}\right] + \left({x \, \bmod \, 1}\right)$

where $\left[{x \notin \Z}\right]$ uses Iverson's convention.

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left \lceil {x + y} \right \rceil\)	\(=\)	\(\displaystyle \left \lceil {\left \lfloor {x}\right \rfloor + \left({x \, \bmod \, 1}\right) + \left \lfloor {y}\right \rfloor + \left({y \, \bmod \, 1}\right)} \right \rceil\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left \lceil {\left \lceil {x}\right \rceil - \left[{x \notin \Z}\right] + \left({x \, \bmod \, 1}\right) + \left \lceil {y}\right \rceil - \left[{y \notin \Z}\right] + \left({y \, \bmod \, 1}\right)} \right \rceil\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left \lceil {x}\right \rceil + \left \lceil {y}\right \rceil + \left \lceil {\left({x \, \bmod \, 1}\right) + \left({y \, \bmod \, 1}\right)} \right \rceil - \left[{x \notin \Z}\right] - \left[{y \notin \Z}\right]\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	as $\left \lceil {x + n}\right \rceil = \left \lceil {x}\right \rceil + n$: Definition of Ceiling Function

It is clear that $x \notin \Z \implies x \, \bmod \, 1$.

As $0 \le x \, \bmod \, 1 < 1$ it follows that $\left[{x \notin \Z}\right] \ge x \, \bmod \, 1$.

Hence the inequality.

The equality holds iff:

$\left \lceil {\left({x \, \bmod \, 1}\right) + \left({y \, \bmod \, 1}\right)} \right \rceil = \left[{x \notin \Z}\right] + \left[{y \notin \Z}\right]$

that is, iff one of the following holds:

• $x \in \Z$, in which case $x \, \bmod \, 1 = 0$
• $y \in \Z$, in which case $y \, \bmod \, 1 = 0$
• both $x, y \in \Z$, in which case $\left({x \, \bmod \, 1}\right) + \left({y \, \bmod \, 1}\right) = 0$
• both $x, y \notin \Z$ and $\left({x \, \bmod \, 1}\right) + \left({y \, \bmod \, 1}\right) > 1$.

$\blacksquare$