2
$\begingroup$

During class, we were introduced to a proof that used the ceiling function. We assumed (without proof) that:

$$ \left\lceil{\frac{n}{2^i}}\right \rceil= \left\lceil{\frac{\lceil{\frac{n}{2}}\rceil}{2^{i-1}}}\right\rceil,$$

for $i \geq 1$, where $d$ is a positive integer.

I am interested in seeing how this can be proved. I don't know much about the ceiling function, other than its basic properties. I found a general result here , which says for positive integers $m$, $n$ and arbitrary real number $x$.

$$ \left\lceil{\frac{x}{mn}}\right \rceil= \left\lceil{\frac{\lceil{\frac{x}{m}}\rceil}{n}}\right\rceil,$$

$\endgroup$
6
$\begingroup$

I’ll prove the more general result. Let $m$ and $n$ be positive integers and $x$ a real number. Let $k=\left\lceil\dfrac{x}m\right\rceil$. Then $$k-1<\frac{x}m\le k\;,$$ and hence $$\frac{k-1}n<\frac{x}{mn}\le\frac{k}n\;.$$

We want to show that $$\left\lceil{\frac{x}{mn}}\right \rceil=\left\lceil{\frac{\left\lceil{\frac{x}{m}}\right\rceil}{n}}\right\rceil=\left\lceil\frac{k}n\right\rceil\;.$$

Clearly $\left\lceil{\dfrac{x}{mn}}\right\rceil\le\left\lceil\dfrac{k}n\right\rceil$, so suppose to get a contradiction that $\left\lceil{\dfrac{x}{mn}}\right\rceil<\left\lceil\dfrac{k}n\right\rceil$. Then there must be an integer $\ell$ such that

$$\frac{x}{mn}\le\ell<\frac{k}n$$

and hence $\dfrac{x}m\le n\ell<k$. But then $k=\left\lceil\dfrac{x}m\right\rceil\le n\ell<k$, which is absurd.

$\endgroup$
  • $\begingroup$ I like it! Thanks! $\endgroup$ – Maria Nov 9 '12 at 19:49
  • $\begingroup$ @Maria: You’re welcome! $\endgroup$ – Brian M. Scott Nov 9 '12 at 19:50
  • $\begingroup$ @DAS: Try $x=1$, $m=2$, and $n=-1$. $\endgroup$ – Brian M. Scott Jun 18 '15 at 7:48
  • $\begingroup$ I see, I see. Thanks. $\endgroup$ – DAS Jun 18 '15 at 7:57
  • $\begingroup$ @DAS: You're welcome. $\endgroup$ – Brian M. Scott Jun 18 '15 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.