Sum of Ceilings not less than Ceiling of Sum

Theorem

Let $\ceiling x$ be the ceiling function.

Then:

$\ceiling x + \ceiling y \ge \ceiling {x + y}$

The equality holds:

$\ceiling x + \ceiling y = \ceiling {x + y}$

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

or:

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

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

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

$x = \floor x + \paren {x \bmod 1}$

from which we obtain:

$x = \ceiling x - \sqbrk {x \notin \Z} + \paren {x \bmod 1}$

where $\sqbrk {x \notin \Z}$ uses Iverson's convention.

$\ds \ceiling {x + y}$

$=$

$\ds \ceiling {\floor x + \paren {x \bmod 1} + \floor y + \paren {y \bmod 1} }$

$\ds $

$=$

$\ds \ceiling {\ceiling x - \sqbrk {x \notin \Z} + \paren {x \bmod 1} + \ceiling y - \sqbrk {y \notin \Z} + \paren {y \bmod 1} }$

$\ds $

$=$

$\ds \ceiling x + \ceiling y + \ceiling {\paren {x \bmod 1} + \paren {y \bmod 1} } - \sqbrk {x \notin \Z} - \sqbrk {y \notin \Z}$

We have that:

$x \notin \Z \implies x \bmod 1 > 0$

As $0 \le x \bmod 1 < 1$ it follows that:

$\sqbrk {x \notin \Z} \ge x \bmod 1$

Hence the inequality.

The equality holds if and only if:

$\ceiling {\paren {x \bmod 1} + \paren {y \bmod 1} } = \sqbrk {x \notin \Z} + \sqbrk {y \notin \Z}$

that is, if and only if 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 $\paren {x \bmod 1} + \paren {y \bmod 1} = 0$

both $x, y \notin \Z$ and $\paren {x \bmod 1} + \paren {y \bmod 1} > 1$.

$\blacksquare$