0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$"? $\endgroup$
    – Calvin Lin
    Feb 16 at 16:58
  • $\begingroup$ $$2^{k_{2} + 1} > log_{2}(x)$$ and $$3^{k_{1} - 1} < log_{3}(x)$$ Does that help us somehow? $\endgroup$
    – dayevid_
    Feb 16 at 18:29
  • $\begingroup$ 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? $\endgroup$
    – Calvin Lin
    Feb 16 at 18:50
  • $\begingroup$ 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. $\endgroup$
    – dayevid_
    Feb 16 at 19:14
  • $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Feb 16 at 22:14

3 Answers 3

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ How did you come to the conclusion of saying $(3/2)^{m} < 3$? $\endgroup$
    – dayevid_
    Feb 18 at 16:48
  • $\begingroup$ 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$ $\endgroup$
    – dayevid_
    Feb 18 at 16:53
  • $\begingroup$ From $3^{m-1} \le 2^m$, divide both sides by $2^m$ and multiply by $3$. $\endgroup$ Feb 19 at 0:47
1
$\begingroup$

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

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .