Bien, bueno. Una de las mejores maneras de entender una prueba es reproducirla mediante el recuerdo libre después de echar un vistazo a los componentes básicos de la prueba.
Así que el teorema es:
Sean a y b números enteros; sea $a>b$ . Aplicar el Algoritmo Euclidiano para encontrar el GCD llevará n pasos. El teorema dice que si b tiene $d$ dígitos, entonces $n\leq 5d$ .
Los componentes son el número de Fibonacci y el algoritmo euclidiano, y algunas otras cosas.
En primer lugar, veamos por qué el teorema puede ser cierto.
En primer lugar, veamos el algoritmo euclidiano. ¿Qué hace? Miramos en la wikipedia y vemos que
Dado $a, b$ primero encontramos $b_1 = a\mod b$ y, a continuación, establecer $a_1=b$ .
En el $i$ 'th paso, encontramos $b_{i} = a_{i-1} \mod b_{i-1}$ y a continuación, establecer $a_{i} = b_{i-1}$ . El algoritmo termina en el paso n cuando encontramos que $b_n=0$ .
¿Tiene sentido el teorema? ¿Debería haber un límite máximo para el número de pasos que el algoritmo tomará.
Bueno, sí, por supuesto.
En primer lugar, observamos que $b_{n-1} \geq 1$ .
En segundo lugar, veamos un ejemplo. Dejemos que $b_{i-2} = 30 = {a_{i-1}}$ ¿Cuál es el máximo posible? $b_i$ ? Bien, digamos que $b_{i-1}$ puede ser cualquier cosa. Lo que dará el mayor $b_i$ ?. Bueno, el punto es, $30 \pmod {b_{i-1}}$ no puede ser mayor que $14$ . Así, podemos ver que $b_i < \frac{1}{2}b_{i-2}$ .
Esto ya nos da un límite. Ya ves, $2^4>10$ Así que $b_i$ tiene al menos un dígito menos que $b_{i-8}$ .
Ahora, queremos un vínculo más fuerte. El otro componente importante son los números de Fibonacci.
Veámoslos.
1,2,3,5,8,13,21,34,55,89, 144 ...
Podemos ver inmediatamente que para cada número, si miras 5 números más, hay al menos un dígito más.
Así que, si podemos relacionar lo nuestro con la secuencia de Fibonacci, sería genial.
Pues sí.
Ya hemos dicho que $b_n = 0$ . El valor más pequeño $b_{n-1}$ podría ser es $b_{n-1} = 1$ . (En caso de que necesite justificar esto, considere las otras posibilidades. Debe ser un número entero. Si es 0, entonces el algoritmo habría terminado en el $n-1$ paso. Pero ya designamos a n como el paso en el que termina). Pues bien, ¿qué tal si $b_{n-2}$ ?
Bueno, en primer lugar, vemos que $b_i<b_{i-1}$ . Esto debería ser obvio ya que $b_i$ es el resto de algo dividido por $b_{i-1}$ .
Por lo tanto, el más pequeño $b_{n-2}$ podría ser es $2$ .
Ahora, procedamos.
¿Cuál es el menor $b_{n-3}$ podría ser. Bueno, para conseguir $b_{n-1}$ , hemos dividido $a_{n-2} = b_{n-3}$ por $b_{n-2}$ y encontró el resto. Por lo tanto, $a_{n-2}=b_{n-3} = c\times b_{n-2}+b_{n-1}$ . Obviamente, esto es mayor o igual que $b_{n-2}+b_{n-1}$ .
Ahora, podemos generalizar esto, ¿no? Digamos que sabemos que $b_i$ y $b_{i-1}$ . Bueno, sabemos que $b_i = b_{i-2} \mod b_{i-1}$ Así que $b_{i-2} = cb_{i-1}+b_i \geq b_{i-1} + {b_i}$ . $$$$$$$$
¿Qué aspecto tiene esto? Pues la secuencia de Fibonacci.
¡GENIAL!
De acuerdo, parece que el $b_{n-j}$ no puede ser menor que el número j de la secuencia.
Hay un punto sutil aquí. No lo hemos demostrado. Sólo hemos demostrado que $b_{n-1} \geq 1$ , $b_{n-2}\geq 2$ y que $b_{i-2}\geq b_{i-1}+b_{i} $ .
Queremos demostrar que el menor valor posible de $b_{n-j}$ es el número j de la secuencia. Así que...
Todavía tenemos que demostrar que el menor valor posible de $b_{i-2}$ es mayor que la suma del menor valor posible de $b_{i-1}$ y $b_{i}$ . Esto es bastante fácil de probar.
Para cualquier $b_{i-2}$ tenemos que $b_{i-2} \geq b_{i-1} + b_{i} \geq \min(b_{i-1})+ \min(b_{i})$ . Como tal, $\min (b_{i-2})\geq \min(b_{i-1})+ \min(b_{i})$ .
Así que ahora, demostramos que $b_{n-j}$ es mayor o igual que $F_j$ el $j'$ término de la secuencia de Fibonacci.
Es cierto para $j=1$ y $j=2$ . $b_{n-1}>\geq 1$ y $b_{n-2}\geq 2$ .
Si es cierto para $j=k$ y $j=k+1$ , entonces dejemos que $i=(n-k)$ . Así que, $b_{n-(k+2)} = b_{i-2}$ . $b_{n-(k+1)} = b_{i-1}$ . $b_{n-k} = b_i$ . Entonces vemos que $\min(b_{n-(k+2)}) = \min(b_{i-2}) \geq \min(b_{i-1})+ \min(b_{i}) = F_{k+1}+F_{k} = F_k$ .
Así que, $b_{n-(k+2)} \geq F_{k+2}$ por lo que la afirmación es cierta para $j=k+2$ .
Por inducción matemática tenemos entonces que la afirmación es verdadera para todos los enteros $j$ .
¿Qué hemos demostrado hasta ahora?
Bueno, hemos demostrado que $b_{n-n} = b \geq F_n$ . En otras palabras, la forma Knuth del teorema.
Ahora, ¿qué tal el original?
Bien, sólo tenemos que dar la prueba de que cada aumento de decimales para la secuencia de Fibonacci lleva como máximo 5 pasos.
Así que.
Hagamos eso.
\begin{align} F_{n+5} & = f_{n+4}+f_{n+3}\\ & = f_{n+3} + f_{n+2} + f_{n+3}\\ & = 2f_{n+3}+f_{n+2}\\ & = 2f_{n+2}+2f_{n+1}+f_{n+2}\\ & = 3f_{n+2}+2f_{n+1}\\ & = 5f_{n+1}+3f_n\\ & = 8f_n+5f_{n-1}\\ & = 13f_{n-1}+8f_{n-2}\\ & = 10f_{n-1}+3f_{n-1}+8f_{n-2}\\ & = 10f_{n-1}+11f_{n-2}+3f{n-1}\\ & >10f_n \end{align}
Así que tenemos lo que queríamos. $F_n > 10 F_{n-5}$ . Entonces, empezamos con b. Después de 5 pasos del algoritmo, $b$ tiene un decimal menos. Si b tiene d decimales, entonces después de $5(d-1)$ pasos, b sólo tiene 1 decimal.
Por lo tanto, hemos terminado.
Me gustaría señalar que la definición del primer paso aquí podría ser ligeramente diferente, por lo que la respuesta podría estar fuera de 1.
Pero en general, así es como se haría.
Una vez más, la mejor manera de entender una prueba es replicarla mediante el recuerdo libre.
0 votos
Quizá sea mejor que nos diga qué parte(s) no entiende, y a partir de ahí podremos ayudarle.