Proving ceil(ceil(x)/a) = ceil(x/a) using Optimization

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 latex-image-5.png 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 latex-image-8.png and latex-image-9.png are identical except that the feasible region of the latter is a subset of the former since


Consequently, the solution of latex-image-9.png will be larger than that of latex-image-8.png. Therefore,


which is a necessary and sufficient condition for


This completes the proof.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s