5
$\begingroup$

I'm to answer if the following holds. But I really don't know how to start approaching it at all.

$$\forall x\geq1 :\lceil \log\lceil x \rceil \rceil = \lceil \log x \rceil $$

The logarithm is base $10$.

I can convert each of the sides into inequalities.

$$ \log x \leq \lceil \log x \rceil \leq (\log x) +1$$ $$ \log \lceil x \rceil \leq \lceil \log \lceil x \rceil \rceil \leq (\log \lceil x \rceil) +1$$

But I really don't know how to bite the ceiling inside the log so I can proceed. How should I think about this problem what do I need to crack it?

$\endgroup$
1
  • $\begingroup$ Indeed, this will hold if your log is to base 10 (or any other integer base), but not if its base is a non-integer. For example, if log is to base e, then the statement fails for all $x\in(2,e)$. $\endgroup$ Aug 14, 2016 at 19:13

2 Answers 2

7
$\begingroup$

The trick is to write your inequalities "inside out." Let $k$ be a positive integer, then

$$ \begin{aligned} \lceil \log {\lceil x \rceil} \rceil = k &\iff k - 1 < \log {\lceil x \rceil} \leqslant k \\ &\iff 10^{k-1} < \lceil x \rceil \leqslant 10^k \\ &\iff 10^{k-1} < x \leqslant 10^k\\ &\quad\quad\text{[reverse the steps ...]} \\ &\iff \lceil \log x \rceil = k. \end{aligned} $$

This proves the result for $x > 1$; the special case $x = 1$ is obvious.

Note that you can drop the inner ceiling only because $10^{k-1}$ and $10^k$ are integers -- this is why the base must be integral. In general, for integer $n$ and real $x$,

$$\begin{aligned}n < \lceil x \rceil &\iff n < x;\\ n \leqslant \lfloor x \rfloor &\iff n \leqslant x;\\ n > \lfloor x \rfloor &\iff n > x;\\ n \geqslant \lceil x \rceil &\iff n \geqslant x.\end{aligned}$$

By the way, many similar identities hold, for example:

$$\Big\lfloor \sqrt {\lfloor x \rfloor} \Big\rfloor = \big\lfloor\sqrt x \big\rfloor,\quad x \geqslant 0;\\ \bigg\lfloor \frac{x+m}{n} \bigg\rfloor = \bigg\lfloor \frac{\lfloor x\rfloor +m}{n} \bigg\rfloor,\quad\begin{aligned}&\text{integer}\;m,\\ &\text{integer}\;n > 0;\end{aligned}$$

etc. A sufficient (but not necessary) condition for $\lfloor f(\lfloor x \rfloor)\rfloor = \lfloor f(x) \rfloor$ is that $f$ be strictly monotonically increasing and the preimage of each integer be an integer. Same holds for ceilings, and also of course $\lfloor f(\lceil x \rceil)\rfloor = \lfloor f(x) \rfloor$ (and "vice versa") if $f$ is decreasing.

Source: Graham, Knuth, and Patashnik - Concrete Mathematics, chapter 3.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you for extremely detailed answer. $\endgroup$ Aug 15, 2016 at 13:50
  • $\begingroup$ You're welcome! $\endgroup$ Aug 16, 2016 at 0:06
1
$\begingroup$

Start by the observation that $\lceil \log y \rceil$ is the smallest integer $n$ such that $y \le b^n$ where $b$ denotes the basis of your logarithm. In your case $b=10$.

You then can think about whether there can exists some $x$ and $n$ such that $x \le b^n$ yet $\lceil x \rceil > b^n$.

As was mentioned in a comment the answer to this depends on whether $b$ is integral or not. Since in your case it is integral, it is not hard to see that this is impossible and thus the two are equal.

$\endgroup$

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.