guardia G es la condición i = m. Por I y II, se conoce que para todos los enteros n 1, después de n iteraciones del bucle, I(n) es verdadero. Así...

guardia G es la condición i = m. Por I y II, se conoce que para todos los enteros n 1, después de n iteraciones del bucle, I(n) es verdadero. Así que, después de m ฀ 1 iteraciones del bucle, I(m) es verdadero, que implica que i m y G es falso. IV. Corrección de la post-condición: Suponga que N es el número mínimo de iteraciones después de que G es falso e I(N) es verdadero. Entonces (debido a que G es falso) i m y (porque I(N) es verdadero) i N 1 y suma A[1] A[2] … A[N 1]. Agrupando todo esto da m N 1 y así suma A[1] A[2] … A[m], que es la post-condición. 10. Sugerencia: Suponga que G I(k) es verdadero para un entero k no-negativo. Entonces aantiguo = 0 y bantiguo = 0 y 1) aantiguo y bantiguo son enteros no-negativos con mcd(aantiguo, bantiguo) mcd(A, B). 2) A lo más uno de los dos, aantiguo y bantiguo, es igual a 0. 3) 0 aantiguo bantiguo A B ฀ k. Debe demostrarse que I(k 1) es verdadero después de la iteración del bucle, lo que significa que es necesario demostrar que: 1) anuevo y bnuevo son enteros no-negativos con mcd(anuevo, bnuevo) mcd(A, B). 2) A lo más uno de los dos, anuevo y bnuevo, es igual a cero. 3) 0 anuevo bnuevo A B ฀ (k 1). Para demostrar (3), observe que: anuevo bnuevo aantiguo ฀ bantiguo bantiguo si aantiguo bantiguo bantiguo ฀ aantiguo aantiguo si aantiguo bantiguo [La razón para esto es que cuando aantiguo bantiguo, entonces anuevo aantiguo ฀ bantiguo y b nuevo b antiguo y cuando aantiguo b antiguo, entonces bnuevo bantiguo ฀ aantiguo y anuevo aantiguo.] Así anuevo bnuevo aantiguo si aantiguo bantiguo bantiguo si aantiguo bantiguo Pero como aantiguo = 0, bantiguo = 0 y son enteros no-negativos, entonces aantiguo 1 y bantiguo 1. Entonces aantiguo ฀ 1 0, bantiguo฀ 1 0, aantiguo aantiguo bantiguo ฀1 y bantiguo bantiguo aantiguo ฀ 1. Se tiene que anuevo bnuevo aantiguo bantiguo ฀1 (A B ฀k)฀1 porque (3) tiene validez en la k-ésima iteración. Entonces, por simplificación algebraica se obtiene que anuevo bnuevo A B ฀ (k 1). Sección 5.6 1. a1 = 1, a2 = 2a1 + 2 = 2 ·1 + 2 = 4, a3 = 2a2 + 3 = 2 ·4 + 3 = 11, a4 = 2a3 + 4 = 2 ·11 + 4 = 26 3. c0 = 1, c1 = 1 ·(c0) 2 = 1 ·(1)2 = 1, c2 = 2(c1) 2 = 2 ·(1)2 = 2, c3 = 3(c2) 2 = 3 ·(2)2 = 12 5. s0 = 1, s1 = 1, s2 = s1 + 2s0 = 1 + 2 ·1 = 3, s3 = s2 + 2s1 = 3 + 2 ·1 = 5 7. u1 = 1, u2 = 1, u3 = 3u2 − u1 = 3 ·1 − 1 = 2, u4 = 4u3 − u2 = 4 ·2 − 1 = 7 9. Por definición de a0, a1, a2,…, para cada entero k 1, (*) ak 3k 1 y (**) ak฀1 3(k ฀ 1) 1. Entonces ak฀1 3 = 3(k − 1) + 1 + 3 = 3k − 3 + 1 + 3 = 3k + 1 = ak 11. Por definición de c0, c1, c2,…, cn 2n ฀ 1, para cada entero n 0. Sustituimos k y k ฀ 1 en lugar de n para obtener: (*) ck 2k ฀ 1 y (**) ck฀1 2k฀1 ฀ 1 para todos los enteros k 1. Entonces: 2ck฀1 1 2(2k฀1 ฀ 1) 1 sustituyendo (**) 2k ฀ 2 1 2k ฀ 1 por álgebra básica ck sustituyendo (*) 13. Por definición de t0, t1, t2,…, tn 2 n, para cada entero n 0. Sustituir k, k ฀ 1 y k ฀ 2 en lugar de n para obtener * tk 2 k ** tk฀1 2 k ฀ 1 y *** tk฀2 2 k ฀ 2 Para cada entero k 2. Entonces 2tk฀1 ฀ tk฀2 2 2 k ฀ 1 ฀ 2 k ฀ 2 sustituyendo (**) y (***) 2 k 1 ฀ k 2 k por álgebra tk sustituyendo (*). 5.6 Soluciones y sugerencias para los ejercicios seleccionados A-41 A-42 Apéndice B Soluciones y sugerencias para los ejercicios seleccionados 15. Sugerencia: La inducción matemática no se necesita para la demostración. Inicie con el lado derecho de la ecuación y use álgebra para transformarlo en el lado izquierdo de la ecuación. 17. a. a1 2 a2 2 (mueve el disco de arriba del polo A al polo C) 1 (mueve el disco del fondo del polo A al polo B) 2 (mueve el disco de arriba del polo C al polo A) 1 (mueve el disco del fondo del polo B al polo C) 2 (mueve el disco de arriba del polo A al polo C)8 a3 8 1 8 1 8 26 c. Para todos los enteros k 2. ak ak฀1 (mueve el disco k ฀ 1 de arriba del polo A al polo C) 1 (mueve el disco del fondo del polo A al polo B) ak฀1 (mueve el disco de arriba del polo C al polo A) 1 (mueve los discos del fondo del polo B al polo C) ak฀1 (mueve los discos de arriba del polo A al polo C) 3ak฀1 2 18. b. b4 40 e. Sugerencia: Una solución es utilizar inducción matemática y aplicar la fórmula del inciso c). Otra solución es demostrar, por inducción matemática, que cuando se efectúa una muy eficiente transferencia de n discos de un polo a otro, entonces en algún punto todos los discos están en el polo intermedio. 19. a. s1 1 s2 1 1 1 3 s3 s1 1 1 1 s1 5 b. s4 s2 1 1 1 s2 9 20. b. Los polos se denotarán por A, B y C. Calcule c2 empleando la siguiente secuencia de pasos para transferir dos discos de A a B: 1 (mover el disco de arriba para A a B) 1 (mover el disco de arriba de B a C) 1 (mover el disco del fondo de A a B) 1 (mover el disco de arriba de C a A) 1 (mover el disco de arriba de A a B). La secuencia de pasos es la más pequeña posible y así c2 5. Una torre de 3 discos se puede transferir de A a B utilizando la siguiente secuencia de pasos: 1 (mover el disco de arriba de A a B) 1 (mover el disco de arriba de B a C) 1 (mover el disco intermedio de A a B) 1 (mover el disco de arriba de C a A) 1 (mover el disco intermedio de B a C) 1 (mover el disco de arriba de A a B) 1 (mover el disco de arriba de B a C). Después que se han completado estos 7 pasos, el disco del fondo se puede mover de A a B. En ese punto dos discos de arriba están sobre C y una versión modificada de los siete pasos iniciales puede usarse para moverlos de C a B. Así el número total de pasos es 7 1 7 15 y 15 21 4c2 1. 21. b. t3 = 14 22. b. r0 = 1, r1