Q:

Let $g(k)$ be the greatest odd divisor of $k$ show that $ 0< \sum_{k=1}^n \frac {g(k)}{k} - \frac {2n}{3} \lt \frac 23$

Prove that for all positive intergers $n$,
$$ 0< \sum_{k=1}^n  \frac {g(k)}{k} - \frac {2n}{3} < \frac {2}{3}$$
Where $g(k)$ denotes the greatest odd divisor of $k$.

Here's my try:
All numbers $k$ can be written as $k= 2^ts$, for nonnegative $t$ and odd $s$, therefore if $k= 2^ts$, then $\frac {g(k)}{k} = \frac {1}{2^k}$ i.e $\frac {g(k)}{k}$ is equal to $1$ divided by the highest power of $2$ dividing $k$. I first thought of proving the inequality for $k= 2^n (n>1)$. Let $Q= \sum_{k=1}^{2^n}  \frac {g(k)}{k}$, then:
$$Q = \frac {1}{2}q_1 +\frac {1}{2^2}q_2 + \cdots + \frac {1}{2^{n -1}} q_{2^{n -1}}+  \frac {1}{2^n} q_{2^n}+ 2^{n-1} $$.
$q_i$ is the number of times $\frac {1}{2^i}$ is added in the summation. It's easy to notice that $q_{2^n} =1$. $q_i$ for $0< i < 2^n$ would be equal to $2^{n-1-i}$ (comes from this $(2^i)(2(2^{n-1-i})-1)$). Then:
$$Q= 2^{n-1}+ \frac {1}{2^n} + \sum_{i=1}^{n-1}  \frac{1}{2^i} \cdot 2^{n-1-i}  $$
$$Q = 2^{n-1}+ \frac {1}{2^n} + 2^{n-1} \sum_{i=1}^{n-1}  (\frac{1}{4})^i  $$
EDITED
With some algebra we get that:
$$Q - \frac {2}{3} \cdot 2^n= - \frac {4}{3} \cdot 2^{n-1} + 2^{n-1}+ \frac {1}{2^n} + 2^{n-1} \cdot \frac {4^{n-1}-1}{4^{n-1}} \cdot \frac {1}{3} <  \frac {1}{2^n} < \frac {2}{3} $$
Also:
$$ Q - \frac {2}{3} \cdot 2^n = \frac {1}{2^n} - \frac {2^{n-1}}{4^{n-1}} \cdot \frac {1}{3}= \frac {1}{2^n} - \frac {1}{2^{n-1}} \cdot \frac {1}{3}> \frac {1}{2^n} - \frac {1}{2^{n-1}} \cdot \frac {1}{2}= 0$$
Then I would get:
$$ 0< Q - \frac {2}{3} \cdot 2^n < \frac {2}{3}$$
Well, I thought proving the inequality for $k=2^n$ because I had some idea about how many times the powers of $2$ appeared. I then thought that I could go backwards with induction but I'm stuck. I would like to see some other approaches but I would also like to know if it's possible to solve the problem from the point where I am.
I'll appreciate any hints or help, thanks in advance.

A:

Let $v(k)$ be the largest integer $m$ such that $2^m$ divides $k$. As you noted, $\dfrac{g(k)}{k} = 2^{-v(k)}$. 
So, let $S_n = \displaystyle\sum_{k = 1}^{n}\dfrac{g(k)}{k} = \sum_{k = 1}^{n}2^{-v(k)}$. 
Then, we have: 
\begin{align*}
S_{2n} &= \displaystyle\sum_{k = 1}^{2n}2^{-v(k)} 
\\
&= \sum_{k = 1}^{n}2^{-v(2k-1)} + \sum_{k = 1}^{n}2^{-v(2k)} 
\\
&= \sum_{k = 1}^{n}2^{-0} + \sum_{k = 1}^{n}2^{-(1+v(k))} 
\\
&= \sum_{k = 1}^{n}1 + \dfrac{1}{2}\sum_{k = 1}^{n}2^{-v(k)}
\\
&= n + \dfrac{1}{2}S_n
\end{align*}
Also, $S_{2n+1} = \displaystyle\sum_{k = 1}^{2n+1}2^{-v(k)} = 2^{-v(2n+1)} + \sum_{k = 1}^{2n}2^{-v(k)} = 2^{0} + S_{2n} = S_{2n} + 1$. 
We can now proceed by induction. Trivially, $S_1 = 1$, so $S_1 > \dfrac{2}{3}$ and $S_1 < \dfrac{4}{3}$. 
Now, suppose that for some integer $n$, we have $\dfrac{2n}{3} < S_n < \dfrac{2n}{3} + \dfrac{2}{3}$. 
Then, we have: 
$$S_{2n} = \dfrac{1}{2}S_n + n > \dfrac{1}{2}\left(\dfrac{2n}{3}\right) + n = \dfrac{4n}{3} = \dfrac{2 \cdot 2n}{3}$$
$$S_{2n} = \dfrac{1}{2}S_n + n < \dfrac{1}{2}\left(\dfrac{2n}{3}+\dfrac{2}{3}\right) + n = \dfrac{4n}{3} + \dfrac{1}{3} < \dfrac{2 \cdot 2n}{3} + \dfrac{2}{3}$$
$$S_{2n+1} = S_{2n}+1 > \left(\dfrac{4n}{3}\right)+1 > \dfrac{4n}{3}+\dfrac{2}{3} = \dfrac{2(2n+1)}{3}$$
$$S_{2n+1} = S_{2n}+1 < \left(\dfrac{4n}{3}+\dfrac{1}{3}\right)+1 = \dfrac{2(2n+1)}{3} + \dfrac{2}{3}.$$
Hence, $\dfrac{2 \cdot 2n}{3} < S_{2n} < \dfrac{2 \cdot 2n}{3} + \dfrac{2}{3}$ and $\dfrac{2(2n+1)}{3} < S_{2n+1} < \dfrac{2(2n+1)}{3} + \dfrac{2}{3}$.
So by induction, we have that $\dfrac{2n}{3} < S_n < \dfrac{2n}{3} + \dfrac{2}{3}$ for all $n$, as desired.

A:

Since $2^j\mid k$ for each $j\le v_2(k)$ and $\sum\limits_{j=1}^n2^{-j}=1-2^{-n}$, we have
$$
2^{-v_2(k)}=1-\sum_{j=1}^\infty\left[\,2^j\,\middle|\,k\,\right]2^{-j}\tag1
$$
where $[\dots]$ are Iverson brackets. Thus,
$$
\begin{align}
\sum_{k=1}^n\frac{g(k)}k
&=\sum_{k=1}^n2^{-v_2(k)}\\
&=\sum_{k=1}^n\left(1-\sum_{j=1}^\infty\left[\,2^j\,\middle|\,k\,\right]2^{-j}\right)\\
&=n-\sum_{j=1}^\infty\left\lfloor\frac n{2^j}\right\rfloor\frac1{2^j}\tag2
\end{align}
$$
Furthermore, since $\left\lfloor\frac n{2^j}\right\rfloor\le\frac n{2^j}$ with equality iff $n\equiv0\pmod{2^j}$,
$$
\begin{align}
\sum_{j=1}^\infty\left\lfloor\frac n{2^j}\right\rfloor\frac1{2^j}
&\le\sum_{j=1}^\infty\frac n{2^j}\frac1{2^j}\\
&=\frac n3\tag3
\end{align}
$$
and $\left\lfloor\frac n{2^j}\right\rfloor\ge\frac {n-\left(2^j-1\right)}{2^j}$ with equality iff $n\equiv-1\pmod{2^j}$,
$$
\begin{align}
\sum_{j=1}^\infty\left\lfloor\frac n{2^j}\right\rfloor\frac1{2^j}
&\ge\sum_{j=1}^\infty\frac{n-(2^j-1)}{2^j}\frac1{2^j}\\
&=\frac n3-\frac23\tag4
\end{align}
$$
Equality in $(3)$ can only occur if $n\equiv0\pmod{2^j}$ for all $j$ ($\implies n=0$) and equality in $(4)$ can only occur if $n\equiv-1\pmod{2^j}$ for all $j$ ($\implies n=-1$). Therefore, for $n\ge1$,
$$
\frac{2n}3\lt\sum_{k=1}^n\frac{g(k)}k\lt\frac{2n}3+\frac23\tag5
$$

