Prove that for all positive integers x that $\lceil \log_{3}(x)\rceil \leq \lfloor \log_{2}(x) \rfloor$

Question

$$ \implies \text{Let } k_{1} = \lceil{log_{3}(x)}\rceil \text{ and let } k_{2} = \lfloor{log_{2}(x)}\rfloor$$

$$ \implies \text{Then, } 3^{k_{1}} \geq x \text{ and } 2^{k_{2}} \leq x \text{ because of the floor and ceiling.}$$

$$ \implies \text{Since, } 2^{k_{2}} \leq x \text{ we can do the following work:}$$

$$ \implies log_{3}(x) \leq log_{3}(2^{k_{2}}) = k_{2}log_{3}(2) \leq k \text{ since } log_{3}(2) < 1$$

$$ \implies \text{Thus, we can say } log_{3}(x) \leq k_{2}$$

I'm confused on how to continue from here or whether I'm going in the right direction or not. Any help is appreciated, thank you.

Answer 1

Let $m = \lceil \log_3(x) \rceil$ and $n = \lfloor \log_2(x) \rfloor$. Thus $m$ and $n$ are integers, $3^m \ge x > 3^{m-1}$ and $2^{n+1} > x \ge 2^n$. If $n < m$ we'd have $n \le m-1$, and $3^{m-1} < x < 2^{n+1} \le 2^m$, so $(3/2)^m = 3^m/2^m < 3 $. Since $(3/2)^3 = 27/8 > 3$, $m < 3$ and $n < 2$.

Now for $x = 1$, $\lceil \log_3(1) \rceil = 0 = \lfloor \log_2(1) \rfloor$; for $x = 2$, $\lceil \log_3(2) = 1 = \lfloor \log_2(2) \rfloor$; for $x = 3$, $\lceil \log_3(3) = 1 = \lfloor \log_2(3) \rfloor$; for $x \ge 4$, $\lfloor \log_2(x) \rfloor \ge 2$.
So that leaves no possible positive integers $x$ for which we could have $n < m$.

Answer 2

Here's one way of doing it: First, we have to bound $\log(2)$ and $\log(3)$ with left and right Riemann sums

$$\log(2)=\int_1^2 \frac{1}{t}dt<\sum_{k=0}^{9} \frac{1}{10}\frac{1}{1+\frac{k}{10}}=\frac{33464927}{46558512}$$

$$\log(3)=\int_1^3 \frac{1}{t}dt>\sum_{k=1}^{20} \frac{1}{10}\frac{1}{1+\frac{k}{10}}=\frac{2405217121297}{2329089562800}$$

$$\log(3)=2\log(\sqrt{3})<2\log(e)=2$$

This implies

$$\frac{\log(3)}{\log(2)}>\frac{2405217121297}{1674082973175}>1.4$$

For $x\geq 3^{10}$ we have $\log(x)\geq 10\log(3)>10\log(e)=10$. Then for these $x$ we have

$$1+\frac{2\log(3)}{\log(x)}<1+\frac{4}{\log(x)}<1.4<\frac{\log(3)}{\log(2)}$$

$$\frac{1}{\log(3)}+\frac{2}{\log(x)}\leq \frac{1}{\log(2)}$$

$$\frac{1}{\log(3)}+\frac{1}{\log(x)}\leq \frac{1}{\log(2)}-\frac{1}{\log(x)}$$

$$\frac{\log(x)}{\log(3)}+1<\frac{\log(x)}{\log(2)}-1$$

$$\lceil\log_3(x)\rceil\leq \log_3(x)+1<\log_2(x)-1\leq \lfloor \log_2(x)\rfloor$$

For $1\leq x < 3^{10}$ one can manually check that the inequality holds. We conclude

$$\lceil\log_3(x)\rceil\leq \lfloor \log_2(x)\rfloor$$

Answer 3

(From the comments) We have $ 2^{k_2 + 1 } > x > 3^{k_1 - 1} \geq 2^{k_1 -1}$.
The naive conclusion is that $k_2 + 1 \geq k_1 - 1$, which isn't sufficient as yet.

Since $ 3^2 \geq 2^3$, we can strengthen the inequality to $ 3^{k_1 - 1 } \geq 2^{\frac{3}{2} (k_1 - 1) } $.
This gives us $k_2 + 1 \geq \frac{3}{2} ( k_1 - 1)$.

For $ k_1 \geq 5$, we also have $ \frac{3}{2} (k_1 -1 ) \geq k_1 +1$, giving us the chain $k_2 +1 \geq \frac{3}{2} (k_1 - 1) \geq k_1 +1$.
Hence, we only need to verify for the initial cases where $k_1 \leq 4 \Rightarrow x \leq 27$.