Construir secuencias de Farey de forma inductiva

Question

Objetivo: Me gustaría demostrar que $F_{n+1}$ (la secuencia Farey de orden $n+1$ ) se obtiene de la secuencia de Farey $F_n$ de orden $n$ sumando todas las fracciones de la forma $\frac{a+c}{b+d}$ cuando $\frac{a}{b}<\frac{c}{d}$ son vecinos en $F_n$ y $b+d=n+1$ .

Problema: He conseguido demostrar que $\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}$ pero también tengo que demostrar que $\frac{a+c}{b+d}$ es de la forma correcta (es decir, que es una fracción completamente reducida), así que mi pregunta es ¿cómo puedo demostrar que $gcd(a+c, b+d)=1$ ?

Answer 1

Vecinos $\frac{a}{b} \lt \frac{c}{d}$ en la secuencia de Farey satisfacen

$$ bc - ad = 1$$

Ahora $ b(a+c) - a(b+d) = bc - ad = 1$ .

Así, $\text{gcd}(a+c, b+d) = 1$ .

Answer 2

Merece la pena señalar que ésta y otras muchas propiedades relacionadas con las secuencias de Farey tienen pruebas geométricas muy hermosas utilizando la fórmula de Pick y técnicas relacionadas - véase mi responder aquí y sus enlaces.

Answer 3

Puede definir la secuencia de orden de Farey $n$ como la secuencia de fracciones que se producen en el orden de recorrido de la Árbol de Stern-Brocot mientras no descienda a ramas cuyo denominador sea superior a $n$ . Aquí sólo se encuentran fracciones completamente reducidas, por lo que está en orden. Los descendientes de un nodo del árbol se obtienen sumando a su numerador y denominador los de su primer antepasado en el árbol que está en el lado correcto de la misma (tomando $\frac01$ y $\infty=\frac10$ como antepasados últimos para garantizar que siempre haya uno en cada lado).

Si una fracción entre $0$ y $1$ tiene denominador $n+1$ entonces su progenitor en el árbol de Stern-Brocot tiene un denominador menor, y el primer ancestro del progenitor en la dirección adecuada fue el siguiente en el recorrido en orden hasta el nivel $n$ Lo que explica por qué siempre obtienes $\frac{a+c}{b+d}$ entre $\frac ab$ y $\frac cd$ . La relación $bc-ad=1$ se mantiene siempre que $\frac ab$ es el primer ancestro de $\frac cd$ menos que ella o $\frac cd$ es el primer ancestro de $\frac ab$ mayor que ella; esto se deduce por inducción de la construcción, y demuestra que todas las fracciones son reducidas.