Funciones y secuencias problema

Question

La función$F(k)$ se define para enteros positivos como$F(1) = 1$,$F(2) = 1$,$F(3) = -1$ y$F(2k) = F(k)$,$F(2k + 1) = F(k)$ para $ k \ geq 2$. Then $$F(1) + F(2) + \dotsb + F(63)$ $ es igual

$ \begin{array}{lr} (\text{A}) & 1 \\ (\text{B}) & -1 \\ (\text{C}) & -32 \\ (\text{D}) & 32 \\ \end {array} $

Mi enfoque:$F(4)=1$,$F(5)=1$,$F(6)=-1$,$F(7)=-1$ (es decir, todos los valores de$F$ son$1$ o$-1$ ). Intenté encontrar un patrón para el cual$F(x)$ se repita después de cierto número entero, pero probé hasta$F(30)$ y no puedo encontrar una solución. ¿A dónde me voy mal?

Answer 1

Con la inducción se puede mostrar que:$$F(2^k)+\cdots+F(2^{k+1}-1)=0$ $ para$k=1,2,\dots$

Esto se debe a que$F(2^1)+F(2^2-1)=F(2)+F(3)=1+(-1)=0$ y:$$F(2^{k+1})+F(2^{k+1}+1)+\cdots+F(2^{k+2}-2)+F(2^{k+2}-1)=2F(2^k)+\cdots+2F(2^{k+1}-1)$ $

Entonces$$F(1)+\cdots+F(63)=F(1)+\sum_{k=1}^5\left[F(2^k)+\cdots+F(2^{k+1}-1)\right]=F(1)=1$ $

Answer 2

Por fuerza bruta:

$$F(1)=1$ $$$F(2)=1$ $$$F(3)=-1$ $$$F(4)=F(2)=1$ $$$F(5)=F(2)=1$ $$$F(6)=F(3)=-1$ $$$F(7)=F(3)=-1$ $$$F(8)=F(4)=1$ $$$F(9)=F(4)=1$ $$$F(10)=F(5)=1$ $$$F(11)=F(5)=1$ $$$F(12)=F(6)=-1$ $$$F(13)=F(6)=-1$ $$$F(14)=F(7)=-1$ $$$F(15)=F(7)=-1$ $$$F(16)=F(8)=1$ $$$F(17)=F(8)=1$ $$$F(18)=F(9)=1$ $$$F(19)=F(9)=1$ $$$F(20)=F(10)=1$ $$$F(21)=F(10)=1$ $$F(22)=F(11)=1$$$$F(23)=F(11)=1$ $$$F(24)=F(12)=-1$ $$$F(25)=F(12)=-1$ $ $$F(26)=F(13)=-1$ $$$F(27)=F(13)=-1$ $$$F(28)=F(14)=-1$ $$$F(29)=F(14)=-1$ $$$F(30)=F(15)=-1$ $$$F(31)=F(15)=-1$ $$$\ldots$ $

Surge un patrón:

$$F(1)+F(2)+F(3)+F(4)+F(5)+F(6)+F(7)=1$ $$$F(8)+F(9)+F(10)+F(11)+F(12)+F(13)+F(14)+F(15)=0$ $$$F(16)+F(17)+F(18)+\ldots+F(31)=0$ $$$F(32)+\ldots+F(63)=0$ $

Por lo tanto,$$\sum_{i=1}^{63}{F(i)}=F(1)+F(2)+\ldots+F(63)=1+0+0+0=1.$ $

RESPUESTA CORRECTA --- A

Answer 3

PS

Answer 4

Para $k \ge 2$ tenemos: \begin{align} F(2k) &= F(k) \\ F(2k+1) &= F(k) \end{align} Esto significa $$ F(n) = F(\lfloor n / 2 \rfloor) \quad (*) $$ para $n \ge 4$.

Si estamos usando números de base 2 esto significa que tenemos una palabra de longitud $m$, con al menos tres bits $$ n = (1 b_{m-1} \dotsb b_2 b_1)_2 \quad (b_i \in \{0, 1\}) $$ y $(*)$ significa que podemos cambiar a la derecha de la palabra (colocar la broca en la final) y mantener el valor de $F$: $$ F((1 b_{m-1} \dotsb b_2 b_1)_2) = F((1 b_{m-1} \dotsb b_2)_2) \quad (m \ge 3) $$ Repetimos hasta que tenemos menos de tres bits.

En otras palabras \begin{align} F(n) &= F((1 b_{m-1})_2) \\ &= \begin{cases} F(3), & \text{for } b_{m-1} = 1 \\ F(2), & \text{for } b_{m-1} = 0 \end{casos} \\ &= \begin{cases} -1, & \text{for } b_{m-1} = 1 \\ +1, & \text{for } b_{m-1} = 0 \end{casos} \end{align} para $n\ge 4$. Así $$ \sum_{k=4}^{63} F(k) = F(\underbrace{(100)_2}dimm_4) + F((101)_2) + F((110)_2) + F((111)_2) + \\ F(\underbrace{(1000)_2}_8 + \dotsb + F((1111)_2) + \\ F(\underbrace{(10000)_2}_{16} + \dotsb + F((11111)_2) + \\ F(\underbrace{(100000)_2}_{32} + \dotsb + F((111111)_2) \\ $$ Vemos que podemos agrupar las palabras por medio de longitud, y que tenemos tantas palabras con el prefijo $10$ como con el prefijo $11$ en cada grupo, de modo que su $F$ valores de suma cero.

Así, el tratado de la suma se reduce a $$ \sum_{k=1}^{63} = F(1) + F(2) + F(3) = 1 + 1 + (-1) = 1 $$