Me he topado con una demostración del teorema de Lamé que me ha confundido. La prueba es la siguiente:
Demuéstralo: P(b): El número de llamadas recursivas realizadas por el algoritmo Euclid-GCD cuando se ejecuta con entradas $a b$ avec $b<F_{k+1}$ es $<k$ .
Paso base: el autor elige P(1) y P(2) para los casos base.
Paso inductivo: Supondremos que $P(1) , ... , P(b 1)$ es válida para un número entero arbitrario $b 3$ y luego demostrar que $P(b)$ retenciones.
Supongamos que $k$ es el menor número entero tal que $b < F_{k+1}$ . Esto significa que $b F_k$ . Desglosamos el análisis en las dos partes siguientes:
$a(mod b) < F_k$ : En este caso, después de la primera llamada recursiva, el par de números que se utiliza para las siguientes llamadas recursivas es $(b, a(mod b))$ . Ahora bien, como en este caso, a $(mod b) < b$ y $a(mod b) < F_k$ utilizando la hipótesis de inducción, obtenemos que el número de llamadas recursivas adicionales es $< (k1)$ y, por tanto, el número total de llamadas recursivas es $< (k 1) + 1 = k$ .
$a(mod b) F_k$ : En este caso, el par de números después de la primera llamada recursiva es $(b,a (mod b))$ . Sea el par después de la segunda llamada recursiva $(a(mod b),d)$ . Entonces, puesto que $a(mod b) F_k$ y $b<F_{k+1}$ tenemos $d<b+1a(modb)F_{k+1}F_k = F_{k1}$ . Además, puesto que $d<b$ podemos aplicar la hipótesis inductiva para concluir que el número total de llamadas recursivas es $< (k 2) + 2 = k$ .
Los dos casos anteriores demuestran que $P(b)$ retenciones. Por lo tanto, concluimos que $P(n)$ es válida para todos los valores de $n 1$
Tengo un par de preguntas sobre esta prueba:
En primer lugar, para qué sirve esta afirmación en la prueba: "Esto significa que $b F_k$ "?
En segundo lugar, ¿cómo $d<b+1a(modb)F_{k+1}F_k = F_{k1}$ seguir de $a(mod b) F_k$ y $b<F_{k+1}$ ?
