Jtdylktuy

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.

Since $2^jmid k$ for each $jle v_2(k)$ and $sumlimits_{j=1}^n2^{-j}=1-2^{-n}$, we have
$$
2^{-v_2(k)}=1-sum_{j=1}^inftyleft[,2^j,middle|,k,right]2^{-j}tag1
$$
where $[dots]$ are Iverson brackets. Thus,
$$
begin{align}
sum_{k=1}^nfrac{g(k)}k
&=sum_{k=1}^n2^{-v_2(k)}\
&=sum_{k=1}^nleft(1-sum_{j=1}^inftyleft[,2^j,middle|,k,right]2^{-j}right)\
&=n-sum_{j=1}^inftyleftlfloorfrac n{2^j}rightrfloorfrac1{2^j}tag2
end{align}
$$
Furthermore, since $leftlfloorfrac n{2^j}rightrfloorlefrac n{2^j}$ with equality iff $nequiv0pmod{2^j}$,
$$
begin{align}
sum_{j=1}^inftyleftlfloorfrac n{2^j}rightrfloorfrac1{2^j}
&lesum_{j=1}^inftyfrac n{2^j}frac1{2^j}\
&=frac n3tag3
end{align}
$$
and $leftlfloorfrac n{2^j}rightrfloorgefrac {n-left(2^j-1right)}{2^j}$ with equality iff $nequiv-1pmod{2^j}$,
$$
begin{align}
sum_{j=1}^inftyleftlfloorfrac n{2^j}rightrfloorfrac1{2^j}
&gesum_{j=1}^inftyfrac{n-(2^j-1)}{2^j}frac1{2^j}\
&=frac n3-frac23tag4
end{align}
$$
Equality in $(3)$ can only occur if $nequiv0pmod{2^j}$ for all $j$ ($implies n=0$) and equality in $(4)$ can only occur if $nequiv-1pmod{2^j}$ for all $j$ ($implies n=-1$). Therefore, for $nge1$,
$$
frac{2n}3ltsum_{k=1}^nfrac{g(k)}kltfrac{2n}3+frac23tag5
$$

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 = displaystylesum_{k = 1}^{n}dfrac{g(k)}{k} = sum_{k = 1}^{n}2^{-v(k)}$.

Then, we have:

begin{align*}
S_{2n} &= displaystylesum_{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} = displaystylesum_{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.