Induccin matematica

Web Hosting by Netfirms | Free Domain Names by Netfirms




El principio de inducción matemática.

El principio de inducción matemática consiste en lo siguiente:

Una proposición es válida para todo número natural n si:

Es válida para n = 1
De su validez para un número natural cualquiera n = k se desprende su validez para n = k + 1
En la sección de Lógica, en la parte deDemostración Matemática vimos que el principio de inducción matemática se puede expresar simbólicamente de la siguiente manera:

p(1) ^ k[p(k) --> p(k + 1)] --> np(n)
En esa misma sección se estudió la demostración por contradicción. Demostrar una proposición de la forma p --> q, es equivalente a demostrar esta proposición de la forma [((p ^ ~q) --> (r ^ ~r)]. Es decir, la negación de la proposiciónp --> q, vimos que es equivalente a p ^ ~q, que es exactamente lo que consiste la demostración por contradicción, esta nos lleva a una expresión de la forma r ^ ~r, que es una falsedad, en virtud de esto, se concluye que la negación de la proposición p --> q es falsa.

Antes de ver la demostración del Principio de Inducción Matemática, quiero poner en claro lo siguiente:
El antecedente delprincipio de inducción, consta de dos partes:
1. La proposición es válida para n = 1
2. Si la proposición es válida para un número natural cualquiera n = k entonces es válida para el número n = k + 1.
El consecuente del principio de inducción, nos dice que si lo anterior se cumple, es decir si las dos partes del antecedente son válidas para una proposición, entonces esta sigue siendo válida paratodo número natural n.
Ahora bien, la demostración por contradicción, consiste en la negación del consecuente, y hacer válido el antecedente. Para la demostración por contradicción del principio de inducción matemática negamos el consecuente, es decir, la proposición no es válida para todo número natural n, y se hacen válidas las dos partes del antecedente.

Una proposición es válida para todonúmero natural n si:

Es válida para n = 1
De su validez para un número natural cualquiera n = k se desprende su validez para n = k + 1

Demostración.

Supongamos lo contrario, es decir, que la proposición no es válida para cualquier número natural n. Entonces existe un número natural, digamos m tal que:
1) Para n = m la proposición es falsa y:
2) Para todo n menor a m la proposiciónes verdadera.
En otras palabras, m es el primer número natural para el cual resulta falsa la proposición.
Es evidente que m > 1 pues para n = 1 la proposición es verdadera (por la condición 1 primera parte del antecedente del teorema). Además m - 1 es un número natural, ya que m es natural. Pero entonces la proposición es válida para el número natural m - 1 y no lo es para el número naturalsiguiente m. Esto contradice la condición 2 (segunda parte del antecedente del teorema).
Así se ha llegado a una contradicción r ^ ~r. Dicha contradicción resultó al afirmar que la proposición es falsa para cualquier número natural. Por tanto si se cumplen las condiciones iniciales: la proposición es válida para n = 1 y si es válida para el número n = k entonces es válida para el siguiente número n =k + 1, entonces, la proposición es válida para todo número natural n.

Toda demostración que se basa en el principio de inducción matemática se denomina demostración por inducción (por el método de inducción matemática). Tal demostración consta de dos partes, es decir, verificar que se cumplan las dos condiciones:
La proposición es válida para n = 1
La proposición es válida para n = k + 1 silo es para n = k, donde k es un número arbitrario.
Si estas condiciones se cumplen, podemos afirmar, en virtud del principio de inducción matemática, que la proposición es válida para todo número natural.

Antes de pasar a la demostración de identidades de problemas aritméticos, lo mejor es ver un ejemplo de como se utiliza el principio de inducción matemática en algunos ejemplos, así como...