¿Cómo puedo demostrar que una transformación iterada describe todos los enteros Impares?

Question

Esta es una pregunta en la que quiero encontrar "un mejor" camino (o incluso de diferentes maneras) para demostrar mi suposición, sólo para ampliar mi comprensión de problemas similares y de cómo abordarlos. Es una cuestión de estrategia de prueba. (Esto también está relacionado con mis estudios sobre el problema de Collatz)

Observación: este problema era menos difícil de lo que pensaba, véase mi propia respuesta. En cuanto a mi pregunta para un prueba-estrategia es un buen ejemplo de cómo una representación tabular puede ofuscar el problema y desviar la atención de una solución relativamente sencilla.

---

Consideremos la transformación sobre números Impares positivos $$ x_{k+1} = \left\{ \begin{array} {} { 3x_k-1 \over 2} &\qquad \text{ if } x_k \equiv 1 \pmod 4 \\ { 3x_k+1 \over 2} &\qquad \text{ if } x_k \equiv -1 \pmod 4 \end{array} \right. $$ de forma que, por ejemplo, la trayectoria que comienza en $5$ continúa como $ 5 \to 7 \to 11 \to 17 \to \ldots $

Porque los números de la forma $ x \equiv 3 \pmod 6$ no tienen preimagen las tomo como "raíces" y ordeno todas las trayectorias en la siguiente matriz infinita de dos números naturales Impares $ \ge 3$ : $$ \small \begin{array} {r|rrrr} 3 & 5 & 7 & 11 & 17 & 25 & 37 & 55 & \cdots \\ 9 & 13 & 19 & 29 & 43 & 65 & 97 & 145 & \cdots \\ 15 & 23 & 35 & 53 & 79 & 119 & 179 & 269 & \cdots \\ 21 & 31 & 47 & 71 & 107 & 161 & 241 & 361 & \cdots \\ 27 & 41 & 61 & 91 & 137 & 205 & 307 & 461 & \cdots \\ 33 & 49 & 73 & 109 & 163 & 245 & 367 & 551 & \cdots \\ 39 & 59 & 89 & 133 & 199 & 299 & 449 & 673 & \cdots \\ 45 & 67 & 101 & 151 & 227 & 341 & 511 & 767 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$ El número $1$ forma un ciclo $ 1 \to 1 $ y no aparece en esta tabla.

Parece bastante obvio, que tengo todos los números impar positivos en esta tabla, pero ahora mi pregunta:

Q: ¿Cómo puedo empezar y proceder con una prueba, que esta tabla contiene / que esta regla de transformación describe todos los enteros Impares positivos $ \ge 3$ ?

Observación: tal vez mi pregunta no esté formulada de forma óptima, incluso me gustaría recibir ayuda al respecto.

---

Probé, si es útil reformular la transformación de tal manera: $$T: x_k = 4j + r \to x_{k+1}=6j +r \qquad \qquad \text{ for } j \ge 1 , r \in \{-1,1\} $$ entonces mira la inversa y pregunta, si cualquier número de la forma $ x=6j \pm 1$ bajo la transformada inversa tiene una trayectoria, que termina en un número de la forma $3+6i $ .

Pero no tengo ni idea de cómo llegar a una declaración de "integridad".

---

[actualización] tras el comentario de André Nicholas - ansatz transferido a una nueva respuesta

Answer 1

Se puede demostrar por inducción que todo número impar mayor que $1$ está en su mesa :

Si $n = 6k+3$ entonces $n$ es una raíz.
Si $n = 6k+5$ entonces $n = T(4k+3)$ y $1 < 4k+3 < 6k+5$ .
Si $n = 6k+7$ entonces $n = T(4k+5)$ y $1 < 4k+5 < 6k+7$ .

Answer 2

Pista 1: ¿Cuál sería el número entero impar más pequeño que falta en la lista?

Pista 2: Ya has hecho la observación de que un entero impar $\not\equiv 3\pmod6$ tiene una preimagen (que es más pequeña).

Pista 3: El conjunto vacío es el único conjunto de enteros Impares positivos que no tiene un elemento más pequeño. La descenso infinito fue una de las primeras pruebas por inducción.

Answer 3

Consideramos los números impar $ x \ge 3$ . Cualquiera de esos números puede escribirse como $ x = 6j - 3$ o $x=6j-1$ o $x=6j+1 $ con $j \gt 0$ .

Definimos la transformación inversa de la siguiente manera:

elegimos algunos $x_0$ .

• Caso 1: si $x_0$ es de la forma $x=6j -3$ tenemos ese número en nuestro tabla como una entrada "raíz".

• Caso 2: si $x_0$ es de la forma $x=6j +r$ donde $ r \in \{-1,1\}$ nosotros transformamos ese número según

$ \qquad U: x_k = 6j_k + r_k \to x_{k+1} = 4 j_k+r_k $

Porque $x_{k+1}$ es otra vez impar, es otra vez $ x_{k+1} = 4 j_k+r_k = 6j_{k+1} + r_{k+1} $ y de uno de los dos Casos y podemos repetir:

• Caso 1: si es de la forma $x_{k+1} = 6j_{k+1} - 3 $ tenemos de nuevo, que está en la tabla, y con ella todos los números $x_0 \ldots x_k$ en medio.

• Caso 2a: si $ j_k >1 $ tenemos $ x_{k+1} = 4j_k + r_k $ y el menor de esos números es con $j_k = 2$ el número $ x_{k+1} = 4 \cdot 2 -1 = 7 = 6 \cdot 1 +1 $ tal que $j_{k+1}=1$

• Caso 2b: Y si finalmente $ j_k =1 $ tenemos
  $ \qquad \qquad x_{k+1} = 4\cdot 1 -1 = 3$ y esto está en la tabla y cierra la trayectoria o tenemos
  $ \qquad \qquad x_{k+1} = 4 \cdot 1 +1 = 5$ y esto se transforma en $x_{k+2}=3$ que vuelve a cerrar la trayectoria.

Como todas las trayectorias terminan en algún número divisible por 3 y estos números están en la tabla por definición junto con todas sus preimágenes, la tabla dada contiene todos los números naturales Impares $ x \ge 3$ .

(Creo que la forma de argumentar y el formalismo deberían ser mejorables, por favor, señalad cualquier error o debilidad...)