Deje que$g(k)$ sea el mayor divisor impar de$k$ para demostrar que$ 0< \sum_{k=1}^n \frac {g(k)}{k} - \frac {2n}{3} \lt \frac 23$

Question

Probar que para todo positivo intergers $n$,

$$ 0< \sum_{k=1}^n \frac {g(k)}{k} - \frac {2n}{3} < \frac {2}{3}$$

Donde $g(k)$ denota el mayor divisor impar de $k$.

Aquí está mi trate de:

Todos los números de $k$ puede ser escrito como $k= 2^ts$, para no negativo $t$ e impares $s$, por lo tanto si $k= 2^ts$, a continuación, $\frac {g(k)}{k} = \frac {1}{2^k}$ i.e $\frac {g(k)}{k}$ es igual a $1$ dividido por el mayor poder de $2$ dividiendo $k$. Pensé por primera vez de la prueba de la desigualdad de la $k= 2^n (n>1)$. Deje $Q= \sum_{k=1}^{2^n} \frac {g(k)}{k}$, entonces:

$$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$ es el número de veces $\frac {1}{2^i}$ es añadido en la suma. Es fácil notar que $q_{2^n} =1$. $q_i$ para $0< i < 2^n$ sería igual a $2^{n-1-i}$ (viene de esta $(2^i)(2(2^{n-1-i})-1)$). Entonces:

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

EDITADO

Con algunos de álgebra obtenemos que:

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

También:

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

A continuación, me gustaría conseguir:

$$ 0< Q - \frac {2}{3} \cdot 2^n < \frac {2}{3}$$

Bien, pensé en probar la desigualdad de la $k=2^n$ porque tenía alguna idea acerca de cómo muchas veces los poderes de $2$ apareció. Pensé entonces que podía ir hacia atrás con la inducción, pero estoy atascado. Me gustaría ver algunos otros enfoques, pero también me gustaría saber si es posible resolver el problema desde el punto donde estoy.

Apreciaré cualquier sugerencias o ayuda, gracias de antemano.

Answer 1

Deje $v(k)$ ser el entero más grande $m$ tal que $2^m$ divide $k$. Como usted señaló, $\dfrac{g(k)}{k} = 2^{-v(k)}$.

Por lo tanto, vamos a$S_n = \displaystyle\sum_{k = 1}^{n}\dfrac{g(k)}{k} = \sum_{k = 1}^{n}2^{-v(k)}$.

Entonces, tenemos:

\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*}

También, $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$.

Ahora podemos proceder por inducción. Trivialmente, $S_1 = 1$, lo $S_1 > \dfrac{2}{3}$ e $S_1 < \dfrac{4}{3}$.

Ahora, supongamos que para algún entero $n$, tenemos $\dfrac{2n}{3} < S_n < \dfrac{2n}{3} + \dfrac{2}{3}$.

Entonces, tenemos:

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

Por lo tanto, $\dfrac{2 \cdot 2n}{3} < S_{2n} < \dfrac{2 \cdot 2n}{3} + \dfrac{2}{3}$ e $\dfrac{2(2n+1)}{3} < S_{2n+1} < \dfrac{2(2n+1)}{3} + \dfrac{2}{3}$.

Así que por inducción, tenemos que $\dfrac{2n}{3} < S_n < \dfrac{2n}{3} + \dfrac{2}{3}$ para todos los $n$, como se desee.

Answer 2

Desde $2^j\mid k$ por cada $j\le v_2(k)$ e $\sum\limits_{j=1}^n2^{-j}=1-2^{-n}$, tenemos $$ 2^{-v_2(k)}=1-\sum_{j=1}^\infty\left[\,2^j\,\medio|\,k\,\right]2^{j}\tag1 $$ donde $[\dots]$ son Iverson soportes. Por lo tanto, $$ \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} $$ Además, desde el $\left\lfloor\frac n{2^j}\right\rfloor\le\frac n{2^j}$ con igualdad de 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} $$ y $\left\lfloor\frac n{2^j}\right\rfloor\ge\frac {n-\left(2^j-1\right)}{2^j}$ con igualdad de 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} $$ La igualdad en $(3)$ sólo puede ocurrir si $n\equiv0\pmod{2^j}$ para todos los $j$ ($\implies n=0$) y la igualdad en $(4)$ sólo puede ocurrir si $n\equiv-1\pmod{2^j}$ para todos los $j$ ($\implies n=-1$). Por lo tanto, para $n\ge1$, $$ \frac{2n}3\lt\sum_{k=1}^n\frac{g(k)}k\lt\frac{2n}3+\frac23\tag5 $$