Ceiling of logarithm of ceiling of x

Question

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?

Answer 1

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.

Answer 2

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.