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.


Proof.

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

latex-image-2

It is then not hard to see that

latex-image-4.png

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,

latex-image-6.png

while, on the other hand, we have that

latex-image-7.png

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

latex-image-10.png

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

latex-image-11.png

which is a necessary and sufficient condition for

latex-image-12.png

This completes the proof.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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