# 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}$

if and only if 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 = \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}$ Ceiling of Number plus Integer

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$