Probar la inducción matemática con $3n+1$ conjetura

Question

Conjetura de Collatz también se conoce como $3n+1$ conjetura.

Bueno, pensé que ya que la conjetura trata de números naturales, podríamos intentar la inducción matemática y ver por qué no funciona.

Intentaré utilizar la inducción fuerte.

Este es el caso base para $(n=1)$ o $(n=2)$

Sabemos que la conjetura funciona para $n=1$ y $n=2$ .

Así que pasemos a la fase de inducción.

Supongamos que la conjetura se cumple hasta un número natural $k$ por lo que la conjetura se cumple para $ \{1,2,.....,k \}$ . Ahora tenemos que demostrar que también se cumple para $k+1$

Aquí tenemos dos casos (1) $k$ es par (2) $k$ es impar

Empezaremos por el caso más sencillo, el caso (2)

Si $k$ es impar entonces $k+1$ es par y por tanto el primer paso es la división $\frac{k+1}{2}$ estará en la lista $ \{1,2,..........,k \}$ porque $\frac{k+1}{2} < k$ y por lo tanto hemos terminado para este caso.

Sin embargo, la vida no puede ser tan fácil :D

Así que tenemos que considerar el caso (1)

Si $k$ es par entonces $k+1$ es impar y por lo tanto tenemos que multiplicar $3(k+1) + 1 = 3k +4$ y $3k+4$ es par porque impar(3)xpar(k) + par(4) = par + par = par así que aplicaremos el paso de la división $\frac{3k+4}{2}$ Sin embargo, no siempre es cierto que $\frac{3k+4}{2} \leq k$ Y así falla la inducción

¿He hecho algo mal o hay algo que pueda añadir para avanzar un poco más?

Answer 1

No has hecho nada malo, sólo has tropezado con la razón principal por la que esta conjetura es tan difícil. No hay manera de controlar la tasa de crecimiento de este algoritmo para un determinado $k$ . A veces aterrizarás en la región de tu inducción, otras no.

Puede encontrar algunos razonamientos heurísticos para la conjetura aquí junto con más información sobre por qué es difícil.

Answer 2

La vena de la prueba que estás bajando sería funcionar, si pudieras introducir los elementos pertinentes. En particular, la forma que parece querer es:

Si, para cada $k>1$ eventualmente $k$ itera hasta algún $k'<k$ entonces podemos usar la inducción sobre $k$ para demostrar la conjetura de Collatz.

Sin embargo, demostrar la primera parte después de "si" no es trivial; después de todo, es equivalente a la conjetura de Collatz. Probablemente, el principal peligro de este tipo de problemas es encontrar muchas afirmaciones que resultan ser equivalentes a la conjetura de Collatz con sólo examinarlas un poco, lo que suele indicar que sólo se está reformulando el problema, en lugar de avanzar hacia una demostración completa. (Y la cantidad de tiempo que puedes dedicar a esto está limitada únicamente por la amplitud de tus conocimientos matemáticos).

Sin embargo, tu veta de prueba (considerando los números por paridad) sí da una extensión natural para obtener más resultados - en particular, podemos considerar las clases de residuos de $k$ mod $2^n$ - lo que has hecho es manejar el caso mod $2$ :

• Si $k$ es par, entonces itera inmediatamente a algún $k'<k$ .

• Si $k$ es impar, aumenta en el siguiente paso.

Sin embargo, podemos, por ejemplo, ampliar esto para considerar lo que $k$ es mod $4$ .

• Si $k$ es $0$ o $2$ mod $4$ entonces es par, y por lo tanto disminuye.

• Si $k$ es $1$ mod $4$ luego pasa a $3k+1$ que es divisible por $4$ por lo que itera hasta $\frac{3k+1}4$ que es inferior a $k$ (para $k>1$ ).

• Si $k$ es $3$ mod $4$ luego pasa a $3k+1$ es divisible por $2$ una vez, entonces aplicamos $3n+1$ otra vez, y divide por dos otra vez. Sin embargo, esto aumenta $k$ por un factor de $\frac{9}4$ más o menos, así que tenemos problemas.

Y podemos seguir comprobando mod $8$ y así sucesivamente - esencialmente, lo que dice lo anterior es: "Si hay un contraejemplo, entonces el contraejemplo más pequeño es congruente con $3$ mod $4$ ". Wikipedia profundiza un poco más en este hecho - sin embargo, es bastante fácil demostrar que este enfoque nunca puede eliminar cada residuo mod $2^n$ (en particular, un resultado es que $2^n-1$ siempre itera a $3^n-1$ - por lo que el factor de crecimiento es ilimitado, lo que significa un residuo de $-1$ mod $2^n$ aumenta en el transcurso de $n$ pasos), por lo que se requiere un conocimiento adicional.