5.1.- INDUCCIÓN MATEMÁTICA

5.1.- INDUCCIÓN MATEMÁTICA
En matemáticas, la inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:
Premisa mayor: El número entero tiene la propiedad .
Premisa menor: El hecho de que cualquier número entero tenga la propiedad implica que también la tiene (que se anota ).
Conclusión: Todos los números enteros a partir de tienen la propiedad .


5.1.1 PRINCIPIO DE INDUCCIÓN MATEMÁTICA

La inducción matemática se usa a menudo para verificar o probar, una conjetura obtenida mediante inducción no matemática. Hablando con precisión, el axioma de inducción dice: si M es un conjunto de enteros positivos, con las siguientes propiedades
IA. M Contiene al entero 1, y,
IIA. Si M contiene al entero n, se puede demostrar que M contiene además al entero n+1, entonces M contiene a todos los enteros positivos.
La primera parte del axioma de inducción, IA suele llamarse base, y la segunda parte, IIA parte inductiva. El axioma de inducción es útil para demostrar ciertas expresiones matemáticas. Suponiendo que la proposición P(n) es verdadera o falsa dependiendo solo del valor de la n, el axioma de inducción se puede utilizar para demostrar que si
IB. P(1) es verdadera, y
IIB. El saber que P(n) es verdadera, implica que P(n+1) es también verdadera, entonces P(n) se cumple para cualquier n.

Usamos inducción sobre los naturales para: Demostrar que todos los números naturales tienen una cierta propiedad.
Ejemplo. 〖S(n)〗^ =∑_(k=0)^n▒〖k=(n(n+1))/2〗

Definir diversos objetos asociados a los números naturales: Definiciones inductivas/recursivas de funciones relaciones etc. Ejemplo: n!= 1, (n+1)!= (n+1)∗n!
La inducción nos permite demostrar que existe una única función: N→N que satisface las ecuaciones de arriba.
Hay al menos tres principios de inducción para los naturales que son equivalentes.




Principio simple de inducción (PSI)
Dado un subconjunto S de N (S⊆ N), si se cumple que
(I) 0∃ S;
(II) Dado cualquier n∃ N, si n∃ S entonces (n+1)∃ S; entonces S=N.
Principio de inducción por curso de valores
Dado un subconjunto S de N (S⊆ N), si se cumple que para todo nE N:
{kEN : k < n⊆ S⇒ S},(∗) entoces S=N. Aquí vemos que no hay una “base. Explicita”: solo hay un paso inductivo, y En este la HI es {kEN : k < n}⊆ S⇒ S y la TI es nE S. Principio del buen orden El principio del buen orden implica. El principio de inducción matemática Sea A un subconjunto de números naturales tal que, (1) Contiene al 1, y (2) Si contiene a n entonces contiene a n+1. Supongamos que A = N. Sea B=N-A el conjunto de números naturales que no están en A. Si A = N, entonces B= φ. Luego por el principio del buen orden, B tiene Un elemento más pequeño. Sean m∃ B el elemento más pequeño de B. Observar que m = 1 porque 1∃ A. Por lo tanto, m>1 y podemos escribir m= (m-1)+1, y m-1∃ N.
Observar que m-1 no existe B porque el número más pequeño en B es m.
Por lo tanto, m-1∃ A y entonces m= (m-1)+1∃ A.
Esto contradice la suposición”m es el elemento más pequeño de B.”
El principio de inducción matemática implica El Principio Del Buen Orden
Sea A un subconjunto de números naturales.
El principio del buen orden dice:
A = φ⇒∃m∈ A,∀n∈ A,m < n
Esto dice P⇒ Q, lo cual es equivalente a Q o∼ P. Es decir,
∃m∈ A,∀n∈ A,m < noA = φ
Supongamos que∼ Q. Es decir, que, ∀m∈ A,∃n∈ A,m≥ n
Sea B el subconjunto de N tal que 1, 2,3,...,k, no pertenecen a A.
Observar que 1∈ B.
(Porque 1∈ A⇒∀n∈ A,1 < n).
Por el principio de inducción matemática, B=N.
Por lo tanto A=vacio. Es decir, P

P Q PYQ
V V V
V F F
F V F
F F F

P Q POQ
V V V
V F V
F V V
F F F


P Q P Q
V V V
V F F
F V V
F F V

Como dijimos al principio, todos estos principios son equivalentes: cada una se puede demostrar a partir de cualquiera de los otros. A veces uno es más apropiado que otro, según el problema donde requiera aplicar.