R A M A A Z U L I X METODO DE INDUCCION (II) En la entrega anterior, habíamos presentado la versión clásica del principio de inducción completa; para demostrar que cierta proposición es válida para todos los números se puede proceder 1) viendo la validez de P(1); 2) Demostrando el paso inductivo: P(k) implica P(k+1) para todo k. I) PRINCIPIO DE INDUCCION GENERALIZADO Con una ligera modificación en uno de los pasos del método de induc- ción clásico, se obtiene del método de inducción generalizado, que es de uti- lidad cuando se quiere demostrar una proposición que vale desde cierto natural en adelante: se trata simplemente de cambiar la verificación de P(1) por la verificación de la proposición en el primer natural a partir del cual la misma es verdadera. EJEMPLO: 2 n! > n si nº _ 4. P(4) es verdadera: 4! = 4 x 3 x 2 x 1 = 24 y 4² = 16 . Veamos el paso inductivo, para h _ 4 (h+1)! = (h+1).h! > (h+1).h² = h.h² + h² = = (h-1).h² + h² + h² > 2h + 1 + h² = (h+1)² La última desigualdad es cierta, ya que h - 1 > 2, y h² > h > 1. Se sigue, por el principio de inducción generalizado, que n! > n², si n_4. II) PRINCIPIO DE INDUCCION GLOBAL El principio de inducción global es una versión equivalente del prin- cipio de inducción, que tiene la ventaja de permitir usar una hipótesis más amplia en el paso inductivo: 1) Si P(1) es verdadero; 2) Si puedo probar que P(h) es verdadero, suponiendo que P(k) es verdadero para todo k < h; entonces, P(n) es verdadero para todos los naturales n. EJEMPLO: Sea f: N --> N la aplicación definida por n/2 si n es par f(n) = n + 3 si n es impar Probar que, para cada n î N, existe i î N tal que la aplicación reiterada i veces de f a n da 1 ó 3. 3 - P(1) es verdadera, ya que f (1) = f(f(f(1))) = 1 - Supongamos que P(k) es verdadera para todo k < n. Si n es par, entonces f(n) = n/2 . Como n/2 < n estamos en las condiciones de la hipótesis inductiva; por lo tanto, reiterando f llegaremos a 1 ó a 3. Si n es impar, sea pues n = 2 h + 1, h _ 1. Se tiene que f(n) = 2 h + 4, y f(f(n)) = h + 2 . Cualquiera sea h î N: h + 2 ó 2 h + 1 (verificarlo). Si h + 2 < n = 2 h + 1 , podemos aplicar la hipótesis inductiva y concluir que la reiteración de f nos llevará a 1 o a 3. Queda la posibilidad h + 2 = 2 h + 1, o sea, h = 1 , y n = 3. Pero f(f(3)) = 3, así que no es un problema. Hemos probado entonces que P(n) es verdadera si lo es P(k) para todo k < n. En virtud del principio de inducción global, concluimos que P(n) es verdadera para todo n. EJERCICIOS 3 1) ¿Para qué valores enteros positivos de n es verdadera n! > n ! 2) Sea f: N --> N dada por n/2 si n es par f(n) = 3n+1 si n es de la forma 4k+1 3n-1 si n es de la forma 4k-1 ¿A qué conduce la aplicación reiterada de f a cualquier n entero positivo? 3) Sea la sucesión de Fibonacci, a(1), a(2), a(3), .... definida recursivamente por: a(1) = 1, a(2) = 1, a(3) = 2 , a(n) = a(n-1) + a(n-2) si n > 2. _ n Probar que, para todo n entero positivo es a(n) < [ (1 + ¹5) / 2 ] . (Ojo! Hay que ver P(1) y P(2) ). 4) Probar que con una jarra de 7 litros y otra de 5 litros se puede medir cualquier cantidad entera de litros no inferior a 24 litros.