Una endofunción sobre números naturales definida por inducción sobre $n$ .

Question

Una función $f \colon \mathbb{N} \to \mathbb{N}$ cumple las siguientes condiciones, para todos $n \in \mathbb{N}$ :

1. $f(4n) = f(2n) + f(n)$ ;
2. $f(4n + 2) = f(4n) + 1$ ;
3. $f(2n + 1) = f(2n) + 1$ .

Pregunta 1: Demuestre que la cardinalidad del conjunto $S_m := \{n \in \mathbb{N} \mid n < 2^m \text{ and } f(4n) = f(3n)\}$ es $f(2^{m+1})$ .

Pregunta 2: ¿Es cierto que $\lim_{n \to +\infty} f(n) = +\infty$ ?

En mi opinión, las dos preguntas, especialmente la primera, son realmente intrigantes y desafiantes. No tengo respuesta para ninguna de las dos, sólo algunas observaciones preliminares.

Observaciones: Las condiciones anteriores definen $f$ por inducción en $n$ ya que $f(0) = 0$ según la condición 1. Para todos los $n > 0$ Tenemos eso:

• $f(n) = f(n-1) + 1$ si $n$ es impar (según la condición 3);
• $f(n) = f(n-1)$ si $n$ es par y no divisible por $4$ (según las condiciones 2 y 3);
• $f(n)$ disminuye con respecto a $f(n-1)$ si $n$ divisible por $4$ pero no soy capaz de encontrar una ley general.

Conjeturo que $f(2^n) = F(n)$ donde $F(n)$ es el $n$ número de la secuencia de Fibonacci, pero no tengo una prueba de ello

Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$ Definir $F(0) = 0$ , $F(1) = 1$ , $F(n) = F(n - 1) + F(n - 2)$ para $n \geqslant 2$ . Configuración $n = 0$ en la primera relación de recurrencia da como resultado $f(0) = 0$ . Ahora no es difícil demostrar por inducción en $n$ que si la representación binaria de $n$ es $(a_m \cdots a_0)_2$ entonces \begin {reunir*}f(n) = \sum_ {k = 0}^m a_k F(k + 1). \tag {1} \end Para la pregunta 2, ya que (1) implica $f(n) \geqslant F([\log_2 n] + 1)$ entonces $\lim\limits_{n → ∞} f(n) = +∞$ . Para la pregunta 1, se necesita el siguiente lema.
Lema: Para cualquier $a, b \in \mathbb{N}$ , $$f(a + b) \leqslant f(a) + f(b)$$ con la igualdad se mantiene si no hay arrastre en los dígitos que no sean el segundo dígito más bajo al sumar $a$ y $b$ en el sistema binario.
Prueba: Sin pérdida de generalidad, supongamos $a = (a_m \cdots a_0)_2$ y $b = (b_m \cdots b_0)_2$ donde $a_m = b_m = 0$ . Definir $c_{0, k} = a_k + b_k$ para $0 \leqslant k \leqslant m$ . Si $c_{j, 0}, \cdots, c_{j, m}$ están definidos, entonces defina $$c_{j + 1, j} = c_{j, j} \bmod 2,\ c_{j + 1, j + 1} = c_{j, j + 1} + \left[ \frac{c_{j, j}}{2} \right],\ c_{j + 1, k} = c_{j, k}\ (\forall k ≠ j, j + 1).$$ Tenga en cuenta que el $c_{j, k}$ definidos anteriormente implementan el proceso de añadir $a$ y $b$ en el sistema binario, y $a + b = (c_{m, m} \cdots c_{m, 0})_2$ . Para $0 \leqslant j < m$ , \begin {align*}& \peq \sum_ {k = 0}^m c_{j, k} F(k + 1) - \sum_ {k = 0}^m c_{j + 1, k} F(k + 1) \\ &= (c_{j, j} F(j + 1) + c_{j, j + 1} F(j + 2)) - (c_{j + 1, j} F(j + 1) + c_{j + 1, j + 1} F(j + 2)) \\ &= (c_{j, j} - c_{j + 1, j}) F(j + 1) - (c_{j + 1, j + 1} - c_{j, j + 1}) F(j + 2). \end {align*}Si no se produce ningún transporte en el $j$ -décima cifra al sumar $a$ y $b$ entonces $c_{j, j} = c_{j + 1, j}$ y $c_{j + 1, j + 1} = c_{j, j + 1}$ , lo que implica $$\sum_{k = 0}^m c_{j, k} F(k + 1) = \sum_{k = 0}^m c_{j + 1, k} F(k + 1).$$ Por lo demás, $c_{j + 1, j} = c_{j, j} - 2$ y $c_{j + 1, j + 1} = c_{j, j + 1} + 1$ , lo que implica \begin {align*}& \peq \sum_ {k = 0}^m c_{j, k} F(k + 1) - \sum_ {k = 0}^m c_{j + 1, k} F(k + 1) \\ &= 2F(j + 1) - F(j + 2) = F(j + 1) - F(j). \end Si $j = 1$ entonces $\sum\limits_{k = 0}^m c_{j, k} F(k + 1) = \sum\limits_{k = 0}^m c_{j + 1, k} F(k + 1)$ . De lo contrario, $\sum\limits_{k = 0}^m c_{j, k} F(k + 1) > \sum\limits_{k = 0}^m c_{j + 1, k} F(k + 1)$ .así $$\sum_{k = 0}^m c_{j, k} F(k + 1) \geqslant \sum_{k = 0}^m c_{j + 1, k} F(k + 1),$$ donde la igualdad se mantiene si $j = 1$ o no hay transporte en el $j$ -décima cifra al sumar $a$ y $b$ . Por lo tanto, $$f(a) + f(b) = \sum_{k = 0}^m c_{0, k} F(k + 1) \geqslant \cdots \geqslant \sum_{k = 0}^m c_{m, k} F(k + 1) = f(a + b),$$ donde la igualdad se mantiene si no se produce ningún arrastre en los dígitos que no sean el segundo dígito más bajo al sumar $a$ y $b$ .
Ahora volvemos a la pregunta 2. Tenga en cuenta que por definición, $f(4n) = f(2n) + f(n)$ para $n \in \mathbb{N}$ . Para cualquier $m \in \mathbb{N}$ se puede demostrar por el lema que \begin {align*}S_m &= \{n < 2^m \mid f(4n) = f(3n)\N-\N- = \N-{n < 2^m \mid f(3n) = f(2n) + f(n)\N-ES} \\ &= {n < 2^m \mid \text {No hay arrastre en los dígitos que no sean el segundo dígito más bajo} \\ & \peq \text { al sumar } 2n \text { y } n\} \\ &= {n < 2^m \mid \text { No se produce arrastre al sumar } 2n \text { y } n\} \\ &= {n < 2^m \mid \text {No hay dos dígitos adyacentes en la representación binaria de } n \text { son ambos } 1\}, \end {align*}entonces se puede demostrar que $S_m = S_{m - 1} \cup (S_{m - 2} + 2^{m - 1})$ para $m \geqslant 2$ , donde $A + n := \{a + n \mid a \in A\}$ . Desde $S_{m - 1} \cap (S_{m - 2} + 2^{m - 1}) = \varnothing$ entonces $$|S_m| = |S_{m - 1}| + |S_{m - 2}|. \quad \forall m \geqslant 2$$ Por inducción, $|S_m| = F(m + 2) = f(2^{m + 1})$ para $m \in \mathbb{N}$ .

Answer 2

Aunque no tengo una prueba completa del resultado, explico lo que he encontrado para que cualquiera pueda intentar encontrar la prueba.

En primer lugar, calculamos algunos valores de $f$ para utilizarlo más adelante: $$ \begin{array}{|c|c|} \hline n & 0& 1 & 2 & 3 & 4& 5 & 6 & 7 & 8& 9 & 10 & 11\\ \hline f(n)& 0 & 1& 1 & 2 & 2& 3& 3& 4& 3& 4& 4& 5 \\ \hline \end{array} $$

Denota por $F(m):=f(2^{m})$ (como tú). Así que $F(0)=f(1)=1$ , y $F(1)=f(2)=1$ . La condición 1 dice que, para $m\ge 1$ , $$F(m+1)=f(2^{m+1})=f(4\cdot 2^{m-1})=f(2^{m})+f(2^{m-1})=F(m)+F(m-1),$$ así que $\{F(m+1)\}$ es la secuencia de Fibonacci (la secuencia habitual de Fibonacci comienza con $F_0=0$ , $F_1=1$ Así que $F_2=1$ ). Por tanto, se aplican todas las fórmulas explícitas de la secuencia de Fibonacci.

Podemos describir explícitamente la función $f$ en términos de $F$ .

Expresión explícita:

Dejemos que $1\le n<2^{m+1}$ puede escribirse en binario como $n:=\sum_{i=0}^m b_i 2^i$ para $b_i\in \{0,1\}$ . Entonces $$f(n):=\sum_{i=0}^m b_i f(2^i)=\sum_{i=0}^m b_i F(i)$$

Para demostrar esta fórmula sólo hay que ver que verifica las tres propiedades de la definición. Las propiedades 2 y 3 son fáciles. Sólo la propiedad 1 utiliza la recurrencia de Fibonacci, ya que $$f(4n)=\sum_{i=0}^m b_i F(i+2)=\sum_{i=0}^m b_i (F(i)+F(i+1))=\sum_{i=0}^m b_i F(i+1)+\sum_{i=0}^m b_i F(i)=f(2n)+f(n).$$

Recuerda tu notación: $$ S_m=\{n \in \mathbb{N} \mid n < 2^m \text{ and } f(4n) = f(3n)\}.$$

Ahora bien, creo que lo siguiente es cierto:

Conjetura:

Cualquier $n\in S_m$ verifica que $3n<2^{m+1}$ .

Obsérvese que esto dice que hay una gran diferencia entre el elemento más grande de $S_m$ y $2^m-1$ . Por ejemplo, si $m=5$ el elemento más grande de $S_5$ es $21$ , mientras que $2^m-1=31$ (nota $3\cdot 21=63<64=2^6$ ). Y para $m=6$ obtenemos que 42 es el elemento más grande de $S_6$ y $3\cdot 42=126<128=2^7$ . De hecho, debería ser cierto que $$\lfloor \frac{2^{m+1}-1}{3}\rfloor\in S_m$$ por lo que el mayor $n$ verificando que $3n<2^{m+1}$ está en $S_m$ .

Ahora, utilizando la conjetura se puede demostrar por inducción el siguiente resultado, que implica la respuesta a tu pregunta.

Afirmación

Para cualquier $m\ge 1$ tenemos $$S_{m+1}=S_m\sqcup (S_{m-1}+2^m)$$ (donde $S_{m-1}+2^m=\{n+2^m \ | \ n\in S_{m-1}\}$ ).

Obsérvese que la unión es disjunta porque todos los elementos de $S_m$ son inferiores a $2^m$ mientras que el otro conjunto tiene todos los miembros mayores o iguales a igual a $2^m$ . Así que obtenemos $|S_{m+1}|=|S_m|+|S_{m-1}|$ y estamos terminado, ya que $|S(m)|=F(m+1)$ es cierto para $m=0,1,2$ trivialmente.