Como ya sabrán muchos por acá, el conjunto de los números racionales es numerable, es decir, existe una función biyectiva entre el conjunto de los números racionales y el conjunto de los números naturales, o más coloquialmente, todos los números racionales se pueden poner en una lista (en una lista infinita, pero en una lista al fin y al cabo), uno se puede convencer de esto con la siguiente imagen:



Vemos que todo número racional positivo aparece en este arreglo bidimensional (el número está en la celda ), y además se ve que el camino seguido por la flecha alcanza a todos números del arreglo, de ahí se pueden enlistar a los números racionales así:



(Los números entre paréntesis en el arreglo no se cuentan ya que ya se han contado, por ejemplo, , por eso saltamos )

Meter a todos los racionales en una lista ya teniendo metidos a los racionales positivos es muy fácil, la lista simplemente sería así:


Es decir colocar primero el cero, y luego ir intercalando racionales positivos con sus respectivos inversos aditivos.


La Sucesión diatómica de Stern

Se define la sucesión diatómica de Stern de la siguiente manera:






Algunos términos de la sucesión:

La gráfica de los primeros 4096 terminos ( en el eje vertical, en eje horizontal)



Teorema: La función es una biyección de en .

Prueba:
Para demostrar el teorema se prueba que cada par de primos relativos aparece exactamente una vez en la lista:


(Podemos pensar a cada pareja en la lista, como un número racional, es decir representa al número )
(Los números racionales pueden ser representados de distintas maneras, por ejemplo, . Así, si y aparecen en la lista, la función no sería inyectiva. Por esta razón se exige que las parejas de números sean primos relativos, para evitar repeticiones.)


Ahora se define el algoritmo lento de Euclides (SEA) sobre parejas de números positivos: dado un par se resta el número más pequeño del más grande, se repite este procedimiento hasta que ambos sean iguales. Por ejemplo:.

Algunos resultados:

-Este algoritmo siempre termina: Ningún elemento del par puede llegar a ser negativo o cero, ya que el algoritmo resta al más grande el más pequeño, así que lo peor que podría pasar es que uno de los elementos del par llegue a 1 sin que sea igual al otro, pero como 1 es el número más pequeño, empezará a restar de uno en uno al otro número, y claramente ambos números llegarán a ser 1’s y con esto el algoritmo finaliza.

-El máximo común divisor se preserva en cada paso del algoritmo: Para ver que el se conserva en cada paso, supongamos que y .
Como divide a y a , es claro que divide a ,luego, g es divisor común de y . Supongamos que divide a y a , es claro entonces que divide a , ahora, como es el máximo común divisor de y , tenemos que . Por tanto .

- El algoritmo aplicado a finaliza en , con : Es consecuencia inmediata de los dos 2 últimos resultados.

Sea , veamos los siguientes resultados:

1)

Sea , por la definición de la sucesión tenemos que: , de modo que al aplicar el tenemos que .
Para se hace igual.

2) Si , entonces o

Supongase que , vemos entonces que , de esto tenemos que , con lo que y , de modo que , por tanto .
Si se obtiene el otro caso haciendo el mismo procedimiento.

Resultados finales:

A) Para cada número natural , es un par de primos relativos:

Por los resultados 1) y 2), más el hecho de que el se conserve en cada paso y que es un par de primos relativos, se tiene que y son dos pares de primos relativos, por esa misma razon y son parejas de primos relativos, etc.
Con esto es facil ver que para todo se tiene que es un par de primos relativos, esto es, . (se podría probar por inducción fuerte)

Haz clic en la imagen para ampliar

Nombre:	Imagen2.png
Vitas:	1
Tamaño:	12,4 KB
ID:	340678
La figura ilustra (sugiere) el hecho de que cualquier está conectado con .

B) Todo par de primos relativos está en la lista :

Si existe un par de primos relativos que no esté en , entonces todos los sucesores bajo el , incluyendo el no estarían en . Absurdo.

C)Ningún par de primos relativos aparece más de una vez en la lista :

Ningún par de primos relativos aparece más de una vez en la lista, de otra manera, se tendría que existe un número más pequeño tal que para algún . Aplicando un paso del a y a se tiene que . Dado que tenemos que (Esto es debido a que es el número más pequeño tal que existe algún tal que , de esto se tiente que no puede cumplir esa propiedad ya que es más pequeño que ). Una solución posible a esta ultima ecuación es , y vemos además que ya no puede ser solución ya que . Claramente no pueden ser soluciones por la misma razón que no lo es.

Por tanto, la única posible solución es , pero esto implica que , es decir, que , con lo que se tiene que , una contradiccion

En conclusión, de A), B) y C), tenemos que todo par de primos relativos aparece una única vez en la lista (y en la lista no hay parejas que no sean de primos relativos).

QED.

Para ver la prueba original y más cosas curiosas sobre esta sucesión mirar acá.

Ejercicio.
. Todos los terminos de la sucesión serían ceros, ejercicio .