INDUCCIÓN MATEMÁTICA

Si estamos entre matemáticos, la palabra inducción nos sugiere el Principio de Inducción Matemática: Si una propiedad vale para 0 y si siempre que la propiedad vale para un número (natural) vale para su sucesor, entonces la propiedad vale para todos los números (naturales). Este famoso principio se hizo especialmente conocido como uno de los cinco postulados de Peano.

1.     1 es un número natural. (es decir, el conjunto de los números naturales no es vacío)

2.     Si a es un número natural, entonces a+1 también es un número natural (llamado el sucesor de a).

3.     1 no es sucesor de ningún número natural. (primer elemento del conjunto)

4.     Si hay dos números naturales a y b tales que sus sucesores son diferentes entonces a y b son números naturales diferentes.

5.     Axioma de inducción: si un conjunto de números naturales contiene al 1 y a los sucesores de cada uno de sus elementos entonces contiene a todos los números naturales.

La Inducción matemática es definitivamente una forma de deducción. Es una inducción en el sentido en que generaliza a toda una clase a partir de unos pocos ejemplos. Es mas, usualmente la muestra está conformada por un caso, y la clase total es infinita!

La inducción matemática es deductiva, porque la muestra mas una regla acerca de los casos no examinados realmente da información sobre todo elemento de la clase. Así la conclusión de una inducción matemática no contiene más información que la que hay en las premisas. La inducción matemática por lo tanto concluye con certeza deductiva.

Un número es cualquier cosa que sea el número de una clase. En teoría axiomática de conjuntos un número natural es un elemento del mínimo conjunto inductivo, conjunto al que se le da el nombre de conjunto de los números naturales; por inductivo se entiende un conjunto S al que pertenece 0 y tal que si n pertenece a S, n + 1 también pertenece. Con esta definición lo que se está aceptando es que el principio de inducción matemática es inherente al concepto de número natural.

Como bien sabemos para probar una proposición por inducción procedemos como sigue: Mostramos que vale para 0, (o 1 o un determinado número). Luego suponemos que si es cierto para un número n mayor que 0 (o 1 o un determinado número), entonces probamos que vale para n+1. Entonces concluimos que vale para todos los números mayores que 0 (o 1 o un determinado número).

Consideremos una lista p (l), p (2), p (3),... de proposiciones con índices en P. Todas las proposiciones p(n) son verdaderas a condición de que:

§  (B)    p(l) sea verdadera;

§  (I)      p(n + 1) sea verdadera siempre que p (n) sea verdadera.

Nos referiremos a (B); es decir, al hecho que p (l) es verdadera, como la base de la inducción y nos referiremos a (1) como el paso inductivo. En la notación del cálculo preposicional, el paso inductivo es equivalente a:     

La implicación p(n) → p (n + 1) es verdadera para todo n € P.

Ejemplo #1:

Los números obtenidos como se observa en la progresión anterior se llaman triangulares y como vemos se pueden obtener de dos maneras diferentes. Esas igualdades se pueden generalizar hoy con la fórmula:

Demostraremos que:

1+2+3+............+n = [n(n+1)]/2,       “n perteneciente a los naturales (*)

1= [1(1+1)]/2.      Por lo tanto 1 satisface la proposición (*)

Supongamos valida la proposición (*) para k perteneciente a los Naturales, es decir supongamos que:

1+2+3+.........+k = [k (k+1)]/2                   (Hipótesis de inducción).

Demostremos que k-1 también satisface la proposición (*), es decir, demostremos que:

1+2+3+.........+k+ (k+1) = [(k+1) (k+2)]/2

Demostración:

(1+2+3+.......+k)+ (K+1) = [k (k+1)]/2 + (k+1)

= [k (k+1)+2(k+1)]/2

= [(k+1) (k+2)]/2

Luego la proposición (*) es verdadera "n perteneciente a los naturales.

Observe que el Principio de inducción matemática no es en sí mismo una prueba de que p(n) sea verdadera para toda n, pero nos dice que si de alguna manera podemos mostrar (B) e (I), entonces las p(n) son verdaderas. Entonces nuestro trabajo reside en mostrar (B) e (I) que deben verificarse antes de poder aplicar el Principio de la inducción matemática. En la práctica, es común que (B) sea fácil de verificar.

Ejemplo #2:

Los números que hoy conocemos como cuadrados recibieron su nombre en la época de los pitagóricos justamente porque se podían distribuir, como si fueran colecciones de puntos, en forma de cuadrado. Y esa progresión de cuadrados se obtiene sumando los números impares sucesivos.

Hay dos ingredientes básicos para una demostración inductiva válida: la base y el paso inductivo. Además, por si hay alguna duda posible, debe  quedar claro que se está dando una demostración por inducción.

Es importante enfatizar, que no demostramos que “p(n + 1) es verdadera." Simplemente  demostramos una implicación: “si p(n) es verdadera entonces p(n + 1) es verdadera. En cierto sentido demostramos una infinidad de afirmaciones; a saber: p(l): si p(1) es verdadera entonces p(2) es verdadera; si p(2) es verdadera  entonces p(3) es verdadera; si p(3) es verdadera entonces p(4) es verdadera, etc. A continuación aplicamos la inducción matemática para concluir: p (1) es verdadera; p (2) es verdadera; p (3) es verdadera; p (4) es verdadera; etc.

El Principio de inducción matemática es igualmente válido si los índices comienzan con algún entero m distinto de 1: Todas las proposiciones  p (m), p (m + 1), p (m + 2),. . . son verdaderas a condición que:

§  (B)    p(m) es verdadera:

§  (I)      p(n) implica p (n + 1) para toda n ≥ m.

Con frecuencia utilizamos esto con m ≥ 0; es decir, cuando las proposiciones p(n) están indicadas por el conjunto N.

El análisis del método de inducción sugiere algunas variantes. Por ejemplo, en la primera etapa, el valor inicial no necesariamente tiene que ser 1. Si en la primera etapa probamos (por ejemplo) que la propiedad se cumple para n = 10, el método de Inducción nos garantiza que la propiedad se cumple únicamente para n = 10, 11, 12,..., y si probásemos que la propiedad se cumple para n = -3, el método de Inducción nos garantiza que la propiedad se cumple para n = -3, -2, -1, 0, 1, 2,... Sin embargo, en la mayoría de los problemas el paso inicial es n=0 o n=1.

La segunda etapa también es susceptible de modificación. Un ejemplo seria probar que si la propiedad se cumple para algún entero k, se cumple para k+2. En este caso, suponiendo que el valor inicial fuese n = 1, habríamos probado que la propiedad se cumple para n = 1, 3, 5, 7... (Cerciorarse de este hecho). Sin embargo, las modificaciones a la segunda etapa son bastante raras, y con frecuencia pueden evitarse escogiendo adecuadamente la variable de inducción.

Si bien es cierto que la segunda etapa es la que “demuestra” que la propiedad se cumple, la primera tiene una importancia fundamental. Un error común es dar por sentada la primera parte del método y comprobar únicamente la segunda. Este es un error que se debe evitar, pues es necesario tener un punto inicial para que la inducción pueda funcionar.

Ejercicio #3:

Demuestre usando inducción que:

2 + 4+ 6 + 8+..........+ 2n = n(n+1)

·         2 i = n(n+1)

i =1

n=1

“2*1 = 1(1+1)

i =1

·         = 1*2

·         = 2

Suponer valido para n = k

“2i = k (k+1)                 Esto es la hipótesis

i =1

Demostrar para n = k+1

“2i = (k+1) (k+2)

“2i = " 2i + 2(k+1)

= k (k+1) + 2(k+1)

= (k+1) (k+2)

Este proceso puede compararse a una escalera, donde la primera etapa nos da el primer peldaño, y la segunda etapa construye nuevos peldaños a partir de los anteriores. La primera etapa prueba que la propiedad se cumple para n = 1, dándonos un punto de partida. La segunda etapa dice que si sabemos que la propiedad se cumple para algún entero, se cumple para el siguiente. ¡Pero la primera etapa nos dice que la propiedad se cumple para n=1!

Entonces podemos asegurar que la propiedad se cumple para el siguiente entero, es decir, n=2. Como la propiedad se cumple para n=2, la segunda etapa nos dice que se cumple para el siguiente, n=3. Como ahora ya sabemos que se cumple para n=3, la segunda etapa nos dice que la propiedad se cumple para n=4, y así sucesivamente. Esto basta para asegurar que la propiedad se cumple para n=1, 2, 3, 4,..., ya que no importa qué número escojamos, en algún momento la escalera “alcanza” ese número.

Ejercicio #4:

Sean A₁, A₂, A₃,…, A_n n subconjunto cualesquiera de un conjunto U. se demostrará por inducción que:

 Ley de De Morgan generalizada para conjuntos

Sea P(n) la proposición que dice que la igualdad se cumple para cualesquiera n subconjuntos de U dados.

Se probará, por inducción, que P(n) es siempre verdadera para n ≥ 1.

Paso básico: Si n = 1, el resultado es trivial

Paso de inducción: Supóngase que P(n) es verdadera para alguna n ≥ 1, sean A₁, A₂, A₃,…, A_n, n + 1 subconjuntos cualesquiera de U. por tanto, si B = A₁UA₂UA₃U…UA_n. Se tiene:

Por consiguiente, P(n + 1) es verdadera, por inducción, P(n) es verdadera para todas las n ≥ 1.

BIBLIOGRAFÍA:

§  Kenneth A. Ross y Charles R. B. Wright. “Matemáticas Discretas” Prentice Hall, Estados Unidos, 1988.

§  Kolman, B. y Busby, R. C. “Discrete Mathematical Structures for Computer Science” Prentice Hall Inc. Estados Unidos, 1984.

§  Johnsonbaugh, Richard. “Matemáticas Discretas” Grupo Editorial Iberoamérica.