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$

Question

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.

Answer 1

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

Answer 2

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.