$(2^k-1)/k$ is approximately equal to $n/\log n$

Question

Let k be the greates integer such that $2^k+k-2 \leq n$ (where also n is an integer). In this hypothesis $(2^k-1)/k$ is approximately equal to $n/\log n$. [For example it is always between $n/2\log n $ and $n/\log n$].

I cannot convince myself of the above statement. I tried some calculations but they didn't work out.

P.s: $\log$ is the log base 2.

Answer 1

An ugly approach. Clearly, $2^k \leq n$, so since $f$ defined on $[1,\infty)$ by $f(x)=(x-1)/\log_2(x)$ (and $f(1)=\ln 2$) is increasing, you get $$ \frac{2^k-1}{k} \leq \frac{n-1}{\log_2 n} < \frac{n}{\log_2 n} $$ (as long as $n\geq 2$ at least).

For the lower bound, by definition of $k=k(n)$ we have $ 2^{k+1}+k-1 > n $ and in particular, since $k \leq 2^{k+1}$, $$ 2\cdot 2^{k+1} > n $$ Using the same property of $f$, we get $$ \frac{n-1}{\log_2 n}<\frac{2^{k+2}-1}{k+2} $$ which implies (as $n-1 \geq n/2$) $$ \frac{n}{2\log_2 n}<\frac{2^{k+2}-1}{k+2} <\frac{2^{k+2}-1}{k} = 4\cdot\frac{2^{k}-1/4}{k} \leq 8\cdot\frac{2^{k}-1}{k} $$ at the end using $x-1/4 \leq 2(x-1)$ for $x\geq 2$. That gives $$ \frac{n}{16\log_2 n} \leq \frac{2^{k}-1}{k} \leq \frac{n}{\log_2 n} $$

Answer 2

Some thoughts.

Fact 1: Let $n\ge 2$ be an integer. Let $k$ be the greatest integer such that $2^k + k - 2 \le n$. Then $$\frac12 \cdot \frac{n\ln 2}{\ln n} \le \frac{2^k - 1}{k} \le \frac{n\ln 2}{\ln n}. \tag{1}$$ (The proof is given at the end.)

Note: The constant $\frac12$ is best in this sense. When $n = 2^m$ for integer $m\ge 3$, we have $k = m-1$ and $$\frac{\frac{2^k - 1}{k}}{\frac{n\ln 2}{\ln n} } = \frac{(2^{m-1} - 1)m}{2^m(m - 1)} \to \frac12, \quad \mathrm{as}\ m \to \infty.$$

$\phantom{2}$

Proof of Fact 1:

For the right inequality:

For $n = 2, 3$, the desired inequality is directly verified.

In the following, assume that $n \ge 4$.

Let $m := \frac{\ln n}{\ln 2}$.

We have $2^m + m - 2 - n = \frac{\ln n}{\ln 2} - 2 \ge 0$. Thus, $k \le m$.

Note that $x \to \frac{2^x - 1}{x}$ is strictly increasing on $x > 0$. Thus, we have $$\frac{n\ln 2}{\ln n} - \frac{2^k - 1}{k} \ge \frac{n\ln 2}{\ln n} - \frac{2^m - 1}{m} = \frac{\ln 2}{\ln n} > 0.$$

$\phantom{2}$

For the left inequality:

For $n = 2, 3, \cdots, 19$, the desired inequality is directly verified.

In the following, assume that $n \ge 20$.

Let $ s:= \frac{\ln n}{\ln 2} - \frac{5}{4\sqrt n}$.

We have \begin{align*} 2^s + s - 2 - n &= \frac{n}{2} \cdot 2^{1-\frac{5}{4\sqrt n}} + \frac{\ln n}{\ln 2} - \frac{5}{4\sqrt n} - 2 - n\\ &\le \frac{n}{2} \cdot \left(1 + 1 - \frac{5}{4\sqrt n}\right) + \frac{\ln n}{\ln 2} - \frac{5}{4\sqrt n} - 2 - n\\ &= - \frac58\sqrt n + \frac{\ln n}{\ln 2} - \frac{5}{4\sqrt n} - 2\\ &< - \frac58\sqrt n + \frac{\ln n}{\ln 2} - 2\\ &< 0 \end{align*} where we use the Bernoulli inequality to obtain $2^{1-\frac{5}{4\sqrt n}} = (1 + 1)^{1-\frac{5}{4\sqrt n}} \le 1 + 1 - \frac{5}{4\sqrt n}$.

Thus, we have $k \ge s - 1$.

Note that $x \to \frac{2^x - 1}{x}$ is strictly increasing on $x > 0$. It suffices to prove that $$ \frac{2^{s-1} - 1}{s - 1} - \frac12 \cdot \frac{n\ln 2}{\ln n} \ge 0 $$ or $$2^{-\frac{5}{4\sqrt n}} - \frac{2}{n} - 1 + \left(\frac{5}{4\sqrt n} + 1\right)\frac{\ln 2}{\ln n} \ge 0.$$

Using $\mathrm{e}^u \ge 1 + u$ for all $u\in \mathbb{R}$, we have $2^{-\frac{5}{4\sqrt n}} = \mathrm{e}^{-\frac{5}{4\sqrt n}\ln 2} \ge 1 - \frac{5}{4\sqrt n}\ln 2$.

It suffices to prove that $$1 - \frac{5}{4\sqrt n}\ln 2 - \frac{2}{n} - 1 + \left(\frac{5}{4\sqrt n} + 1\right)\frac{\ln 2}{\ln n} \ge 0$$ or $$ - \frac{5}{4\sqrt n}\ln 2 - \frac{2}{n} + \left(\frac{5}{4\sqrt n} + 1\right)\frac{\ln 2}{\ln n} \ge 0.$$ This inequality is true.