While flipping through the recursion section of some algorithms text, I got curious as to whether

Indeed, it is true. Below is a proof I came up with that interestingly enough exploits the fact that any ceiling function can be written as an optimization problem.

### Proof.

Using simple algebra, we may rewrite the nested ceiling expression in question as follows

It is then not hard to see that

To show that the rightmost inequality indeed holds, we turn to the definition of as a minimum over the set of integers. Namely,

while, on the other hand, we have that

where a change of variables *c = ad* is performed to arrive at the final expression. The optimization problems that define and are identical except that the feasible region of the latter is a subset of the former since

Consequently, the solution of will be larger than that of . Therefore,

which is a necessary and sufficient condition for

This completes the proof.