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

$$\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.

• It's not clear to me if this can be continued. $\quad$ For another approach, what can we say about $2^{k_2 + 1}$ and $3^{k_1 - 1 }$? Can we use that to conclude that the inequality is true for "large enough $x$"? Feb 16 at 16:58
• $$2^{k_{2} + 1} > log_{2}(x)$$ and $$3^{k_{1} - 1} < log_{3}(x)$$ Does that help us somehow? Feb 16 at 18:29
• More like $2^{k_2+1} > x > 3^{k_1 - 1 }$, so $k_2 geq k_1 - 2$ is a quick conclusion from $\log 3 > \log 2$. Can we close that gap further? Feb 16 at 18:50
• Sorry I meant to put x and not log, apologies. But with $$k_{2} > k_{1} - 2$$... Wouldn't we want to somehow have the constant be positive instead of negative, I'm not seeing a way to rewrite the inequality. Feb 16 at 19:14
• Right, it gets you close to what you want (a linear inequality), then you have to figure out how to close the gap ("constant be positive"). See Robert's solution for one approach. Feb 16 at 22:14

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

• How did you come to the conclusion of saying $(3/2)^{m} < 3$? Feb 18 at 16:48
• Is it because we know that $\frac{3^{m-1}}{2^{m}} < x/x = 1$ and if we proceed further that just simplifies to $(3/2)^{m} < 3$ Feb 18 at 16:53
• From $3^{m-1} \le 2^m$, divide both sides by $2^m$ and multiply by $3$. Feb 19 at 0:47

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

• For the start, using $3^2 > 2^3$, we can conclude that $\log 3 / \log 2 > 1.5$ without the additional machinery. Feb 16 at 22:11
• That would have been a much better bound Feb 16 at 22:13

(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$$.