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.
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.