<s>[INST] Prove that $0<\sum_{k=1}^n \frac{g(k)}{k} - \frac{2n}{3} < \frac{2}{3}$ Prove
$$0<\sum_{k=1}^n \frac{g(k)}{k} - \frac{2n}{3} < \frac{2}{3}$$
where $g(k)$ is the greatest odd divisor of k
Please Find Holes in my Proof.
Let $k=2m+1$ if we show that the right hand side of the equation is true for odd numbers, then it is true for even numbers since there is a net total of $1/3$ since $g(k)/k = 1$ for odd numbers.
$$\sum_{k=1}^n\frac{g(k)}{k} <\frac{2n}{3} + \frac{2}{3}$$
$$\sum_{k=1}^n\frac{g(k)}{k} <\frac{2(2m+1)}{3} + \frac{2}{3}$$
$$\sum_{k=1}^n\frac{g(k)}{k} <\frac{4m}{3} + \frac{4}{3}$$
From $1$ to $2m+1$ there are $m$ even numbers and $m+1$ even numbers, the value of $\frac{g(k)}{k}$ for even numbers is $\frac{1}{2^{V2(k)}}$ where $V2(k)$ is the exponent of 2 in the factorization of k
$$\sum_{k=1}^n\frac{g(k)}{k}  = m+1 + (m)\frac{1}{2} -((\lfloor{\frac{m}{2}\rfloor \frac{1}{4}) +(\lfloor{\frac{m}{4}\rfloor \frac{1}{8}}})...)$$
$$\leq    m+1 + (m)\frac{1}{2} - (\frac{m}{8} + \frac{m}{32}...) = \frac{4m}{3} + 1 <\frac{2(2m+1)}{3} + \frac{2}{3}$$ 
Solving for the left hand side of the inequality
$$0<\sum_{k=1}^n \frac{g(k)}{k} - \frac{2n}{3}$$ Let $k = 2m$ with the same reasoning as above
$$\sum_{k=1}^n\frac{g(k)}{k}  = m + (m)\frac{1}{2} -((\lfloor{\frac{m}{2}\rfloor \frac{1}{4}) +(\lfloor{\frac{m}{4}\rfloor \frac{1}{8}}})...)$$
$$\geq    m + (m)\frac{1}{2} - (\frac{m}{8} + \frac{m}{32}...) = \frac{4m}{3} + \frac{1}{3} >\frac{2(2m)}{3}$$ 
I'm not sure about the solution since it was a strict inequality to begin with. Is this a correct solution? Any other solutions are welcome
 [/INST] Let me prove a slightly sharper inequality. While it looks slightly more complicated it gives a better insight:
$$ \frac 1{3\cdot 2^{\lfloor \log_2(n)\rfloor}}\,\ \le
   \,\ \sum_{k=1}^n\frac{g(k)}k\ -\ \frac 23\cdot n\,\ \le
   \,\ \frac 23 - \frac 1{3\cdot 2^{\lfloor \log_2(n)\rfloor}}
$$
Even better, the above inequality follows instantly from the
following exact formula:
$$ \sum_{k=1}^n\frac{g(k)}k\ -\ \frac 23\cdot n\,\ =
      \,\ \frac 13\cdot \sum_{k\in E_n} 2^{-k}
  \qquad\qquad (*) $$
where $\ E_n\subseteq\mathbb N\ $ is such that
$$ n\,\ =\ \sum_{k\in E_n}2^k $$
In order to see (*),   it takes two simple lemmas (exercises):


*

*formula (*) holds for $\ n=2^K\ $ for arbitrary non-negative integer K   (then $\ E_n=\{K\}$), namely
$$ \sum_{k=1}^{2^K}\frac{g(k)}k\ -\ \frac 23\cdot 2^K\,\ =
      \,\ \frac 13\cdot 2^{-K}
  \qquad\qquad (\%) $$

*if $\ m\ =\ 2^M+n,\ $ where $\ 2^M>n\ $ then
$$ \sum_{k=2^M+1}^m \frac{g(k)}k\,\ =
    \,\ \sum_{k=1}^n \frac{g(k)}k $$
It may help to see that
$$ k\ =\ 2^s\cdot(2\cdot t-1)\qquad \Longrightarrow\qquad
      \frac{g(k)}k\ =\ 2^{-s} $$
That's all.
</s>