¿Cómo se puede probar para todos $n \in \mathbb N$ que la siguiente secuencia siempre da como resultado $1$ : Elija $m$ $x_1 = m$ $$x_{n+1} = \begin{cases} x_n/2 & \text{if $x_n$ is even} \\ \\ x_n + 1 & \text{if $x_n$ is odd} \end{cases}$$
Respuesta
¿Demasiados anuncios?
He decidido que es más fácil publicar la prueba completa:
Todo número natural $m$ puede escribirse como $m=2^k(2j+1)$ donde $j,k$ son enteros positivos. Iterando $m$ vemos que se necesita exactamente $k$ iteraciones para llegar a $(2j+1)$ que es claramente impar por lo que el siguiente iterado es $2j+2$ entonces $j+1$ . Ahora es fácil demostrar que $j+1<2^k(2j+1)$ y $j+1$ también es un número natural, por lo que puede escribirse de la forma indicada anteriormente. Repitiendo el proceso se obtendrá de nuevo un número natural más pequeño, sin embargo, los naturales están limitados a continuación por $1$ y por lo tanto el proceso debe terminar. Para demostrar que termina en $1$ requiere un poco de trabajo pero también es fácil.
