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,$

1 Answers 1

7

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. But then $k=\left\lceil\dfrac{x}m\right\rceil\le n\ell, which is absurd.

  • 0
    @DAS: You're welcome.2015-06-18