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.