¿Cómo puedo probar que cada número racional se puede expresar como la suma de$1/n$? (para un conjunto de enteros n elegido por un cierto algoritmo)

Question

Así que hay este ejercicio extra en mi libro de texto. Me miró con la TA y ninguno de nosotros podría solucionarlo. El ejercicio dice así:

Deje $\alpha$ ser positivo y racional. A continuación, elija el menor número natural $N_0$ tal que $1/N_0 \leq \alpha$. Ahora vamos a $\alpha_1=\alpha-1/N_0$. Ahora elija $N_1$ como el menor número natural tal que $1/N_1 \leq \alpha_1$ etc.

El ejercicio es demostrar que este algoritmo termina para cada racional $\alpha$. (es decir, en algún punto de $\alpha_i=N_i$ y va a terminar como $0$) Es fácil demostrar que $\alpha_i$ se convierte arbitrariamente pequeño, pero no veo ningún enfoque para demostrar que llegue a cero.

Answer 1

Consideremos un paso del algoritmo: tenemos $\frac kl$, y tomamos $n$ el menor entero positivo tal que $\frac 1n \leq \frac kl$. Además, nos vamos a restringir a la trivial caso de que $n > 1$ (es decir, $\frac kl < 1$).

Pretendemos que en un paso del algoritmo, y el numerador de la fracción siempre disminuye. Puesto que no puede disminuir por debajo de 0, el algoritmo debe terminar. Después de restar, la nueva fracción es $$ \frac kl - \frac 1n = \frac{kn-l}{ln}. $$ Ahora, por supuesto, $n$, fue mínima, por lo $k < \frac l{n-1}$. De lo contrario, podríamos haber utilizado $n-1$. Por lo tanto, $k(n-1) < l$, o en otras palabras, $kn - l < k$. Esto concluye la prueba.

Answer 2

Este es el llamado algoritmo voraz para la descomposición de fracciones en fracciones de unidades. Aquí, una unidad de fracción de una fracción de la forma $\frac{1}{n}$. El algoritmo se remonta a 1202 y es debido a Fibonacci.

La razón por la que el algoritmo termina es que los numeradores de las $\alpha_1, \alpha_2 \ldots \alpha_k \ldots $ son estrictamente decreciente como $k$ aumenta: En cada paso que descomponer un número racional $\frac{p}{q}$

$\underbrace{\frac{p}{q}}_{\alpha_k} = \frac{1}{s+1} + \underbrace{\frac{p - r}{q(s+1)}}_{\alpha_{k+1}}$

para algunos $s$ (que es el elegido para ser la máxima de uno de esos que esta identidad se mantenga).

Finalmente vamos a llegar a un $\alpha_k$ a que denumerator $1$.