otras palabras, la afirmación es que todos los términos de la sucesión satisfacen la ecuación sn 5n ฀ 1. Demuestre que esta es verdadera. Solución a. s0 0, s1 4, s2 6s1 ฀ 5 s0 6 4 ฀ 5 0 24, s3 6s2 ฀5 s1 6 24 ฀ 5 4 144 ฀ 20 124 b. Al utilizar inducción matemática fuerte para demostrar que cada término de la sucesión satisface la ecuación, el paso básico debe demostrar que los dos primeros términos la satisfacen. Esto es necesario porque, de acuerdo con la definición de sucesión, para calcular los valores de los últimos términos se requieren conocer los valores de los dos términos anteriores. Así si el paso básico sólo muestra que el primer término cumple la ecuación, no sería posible utilizar el paso inductivo para deducir que el segundo término satisface la ecuación. En el paso inductivo suponga que para un entero k 1 elegido arbitrariamente, todos los términos de la sucesión de s0 a sk satisfacen la ecuación dada y, después deduzca que sk 1 también debe satisfacer la ecuación. 5.4 Inducción matemática fuerte y el principio del buen orden de los números enteros 271 Demostración: Sea s0, s1, s2, . . . la sucesión definida mediante la especificación de que s0 0, s1 4 y sk 6ak฀1 ฀ 5ak฀2 para todo entero k 2 y sea la propiedad P(n) la fórmula sn 5n ฀ 1 P(n) Vamos a utilizar la inducción matemática fuerte para demostrar que para todo entero n 0, P(n) es verdadera. Demostración de que P(0) y P(1) son verdaderas: Para establecer P(0) y P(1), debemos demostrar que s0 50 ฀ 1 y s1 51 ฀ 1. P(0) y P(1) Pero, por definición de s0, s1, s2, . . . , tenemos que s0 0 y s1 4. Ya que 50 ฀ 1 1 ฀ 1 0 y 51 ฀ 1 5 ฀ 1 4, los valores de s0 y s1 de acuerdo con los valores dados por la fórmula. Demostración de que para todo entero k 1, si P(i) es verdadera para todo entero i de 0 a k, entonces P(k 1) también es verdadera: Sea k un número entero con k 1 y supongamos que si 5i ฀ 1 para todo entero i con 0 i k. hipótesis inductiva Debemos demostrar que sk 1 5k 1 ฀ 1. P(k 1) Pero puesto que k 1, tenemos que k 1 2 y así sk+1 = 6sk − 5sk−1 = 6(5k − 1) − 5(5k−1 − 1) = 6 ·5k − 6 − 5k + 5 = (6 − 1)5k − 1 = 5 ·5k − 1 = 5k+1 − 1 por definición de s0, s1, s2, . . . por definición de hipótesis multiplicando y aplicando una ley de los exponentes factorizando el 6 y haciendo aritmética por aritmética aplicando una ley de exponentes, [como se quería demostrar]. [Como hemos demostrado tanto el paso básico como el paso inductivo de la inducción matemática fuerte, llegamos a la conclusión de que el enunciado es verdadero.] Otro uso de la inducción fuerte es el cálculo de productos. Se puede calcular un producto de cuatro números de muchas de maneras diferentes como lo indica la colocación de los paréntesis. Por ejemplo, ((x1x2)x3)x4 significa multiplicar x1 y x2, multiplique el resultado por x3 y después multiplique ese número por x4. Y (x1x2)(x3x4) significa multiplicar x1 y x2, multiplique x3 y x4 y después tome el producto de los dos. Observe que en los dos ejemplos anteriores, aunque los factores se multiplican en un orden diferente, el número de multiplicaciones —tres— es el mismo. Se utiliza inducción mate- mática fuerte para demostrar una generalización de este hecho. 272 Capítulo 5 Sucesiones, inducción matemática y recurrencias Convención Acordamos decir que un solo número x1, es un producto con un factor y se puede calcular con cero multiplicaciones. Ejemplo 5.4.3 Número de multiplicaciones necesarias para multiplicar n números Demuestre que para cualquier entero n 1, si x1, x2, . . . , xn son n números, entonces no importa cómo se insertan los paréntesis en su producto, el número de multiplicaciones que se utilizan para calcular el producto es n ฀ 1. Solución La veracidad del paso básico se sigue inmediatamente de la convención de un producto con un factor. El paso inductivo se basa en el hecho de que cuando varios núme- ros se multiplican entre sí, cada paso del proceso consiste en multiplicar dos cantidades individuales. Por ejemplo, el paso final para calcular ((x1x2)x3)(x4 x5) es multiplicar (x1x2) x3 y x4 x5. En general, si k 1 números se multiplican, las dos cantidades en el paso final consisten de menos de k 1 factores. Esto es lo que hace posible el uso de la hipótesis inductiva. Demostración (por inducción matemática fuerte): Sea la propiedad P(n) la frase Si x1, x2, . . . , xn son n números, entonces no importa cómo se insertan los paréntesis en su producto, el número de multiplicaciones que se usa P(n) para calcular el producto es n ฀ 1. Demostración de que P(1) es verdadera: Para establecer P(1), debemos demostrar que El número de multiplicaciones necesarias para calcular el producto de x1 es 1 ฀ 1. P(1) Esto es verdadero porque, por convención, x1 es un producto que se puede calcular con multiplicaciones y 0 1 ฀ 1. Demostración de que para todo entero k 1, si P(i) es verdadera para todo entero i entre 1 y k, entonces P(k 1) también es verdadera: Sea k cualquier número entero con k 1 y supongamos que Por todo entero i de 1 a k, si x1, x2, . . . , xi son números, entonces no importa cómo se insertan paréntesis en su producto, el número hipótesis inductiva de multiplicaciones para calcular el producto es i ฀ 1. Debemos demostrar que Si x1, x2, . . . , xk 1 son k 1 números, entonces no importa cómo se insertan paréntesis en su producto, el número de multiplicaciones que se usa para P(k 1) calcular el producto es (k 1) ฀ 1 k. Considere un producto de k 1 factores: x1, x2, . . . , xk 1. Cuando se inserta entre paréntesis para calcular el producto, alguna multiplicación está al final y cada uno de Nota Al igual que muchas definiciones, para casos extremos esta puede parecer extraña, pero esto hace que las cosas funcionen muy bien los dos factores que componen la multiplicación final es un producto de menos de k 1 factores. Sea L el producto de los factores de la izquierda y R el producto de los factores de la derecha y supongamos que L consiste de l factores y R consiste de r factores. Entonces l r k 1, el número total de factores en el producto y 1 l k y 1 r k. Por hipótesis inductiva, la evaluación de L tiene l ฀ 1 multiplicaciones y la evaluación de R tiene r ฀ 1 multiplicaciones. Debido a que se necesita una multiplicación final para evaluar L R, el número de multiplicaciones necesarias para evaluar el producto de todos los k 1 factores es (l ฀ 1) (r ฀ 1) 1 (l r) ฀ 1 (k 1) ฀ 1 k. [Esto es lo que se quería demostrar.] [Como hemos demostrado el paso básico y el paso inductivo de la inducción matemá- tica fuerte, llegamos a la conclusión de que el enunciado dado es verdadero.] La inducción matemática fuerte hace posible una demostración del hecho frecuentemente usado en ciencias de la computación de que todo entero positivo n tiene una representación binaria entera única. La demostración se ve muy complicada, debido a toda la notación necesaria para escribir los distintos pasos. Pero la idea de la demostración es simple. Esta es que si los números enteros más pequeños que n tienen representación única como suma de potencias de 2, entonces la única representación de n como suma de potencias de 2 se puede encontrar tomando la represent