¿Esta suma va al infinito?

Question

Considere la posibilidad de $F(x)$ que los mapas de $\Bbb N$ a $\{\pm 1\}$, de tal forma que si $x$ es impar, entonces $F(x)$ = $$(-1)^{(\frac{x-1}{2})}$$, and if $x$ is even, then $F(x)=F(y)$, where $s$ is the odd number obtained after dividing $x$ by $2$ hasta que sea impar.

No $S_n = \sum_{p=1}^n F(p)$ tiene una fórmula explícita? Y si $n$ tiende a $\infty$ hace la suma de los suplentes o será mentira entre un intervalo o ¿se tienden a $\pm \infty$ ?

Answer 1

Deje $T(n) = \sum_{k\text{ is odd, } k\le n}F(k)$. Fácilmente podemos ver que $T(0)=0$, $T(1)=1$, $T(2)=1$, $T(3)=0$, e $T(n+4)=T(n)$ para todos los $n\ge 0$. Este es $1$ si los dos últimos bits de $n$ (cuando se expresa en binario) son diferentes, y $0$ si son el mismo.

A continuación, $T(\lfloor n/2\rfloor) = \sum_{k\text{ is odd, } k\le \lfloor n/2\rfloor}F(k)=\sum_{k\text{ is odd, } 2k\le n}F(2k)$, $T(\lfloor n/4\rfloor) = \sum_{k\text{ is odd, } 4k\le n}F(4k)$, y así sucesivamente. Cada entero es igual a $2^m k$ para algunos no negativo $m$ e impares $k$. Como ejemplo, podemos tomar una suma, y obtener $$S_n = T(n)+T(\lfloor n/2\rfloor)+T(\lfloor n/4\rfloor)+\cdots = \sum_{m=0}^{\lfloor \log_2 n\rfloor}T(\lfloor n/2^m\rfloor)$$ Cada término es $1$ si dos adyacentes bits de $n$ son diferentes y cero si son iguales - la $1$ poco y el $2$ bits de $T(n)$, $2$ poco y el $4$ bits de $T(\lfloor n/2\rfloor)$, $4$ bits y el $8$ bits de $T(\lfloor n/4\rfloor)$, y así sucesivamente.

Suma a ellos, y a $S_n$ es el número de veces que la secuencia de bits cambia entre $0$ e $1$. Entre los $m$-bits de los números, este puede ser tan bajo como $1$ para $n=2^m-1$ (el primer interruptor, de $0$ en la $2^m$ lugar $1$ en la $2^{m-1}$ lugar, siempre está ahí) o $m$ para $n=\lfloor 2^{m+1}/3\rfloor$.

Por lo tanto, hay que es - una forma explícita para $S_n$, y una secuencia $1,2,5,10,21,42,85,\dots$ para que $S_n$ va a la $\infty$.