4 Extensiones del metodo de induccion matematica

Para probar algunas propiedades relacionadas con numeros enteros y subconjuntos de numeros naturales debemos emplear algunas extensiones del Principio de Induccion, como por ejemplo:

1.
Si queremos probar que una cierta propiedad es valida para todo numero natural $\displaystyle n\geq n_{0}$ (siendo $\displaystyle n_{0}$ un numero natural fijo) usando el principio de induccion, debemos seguir los siguientes pasos:
1. a)
  
  Comprobar que el resultado es cierto para $\displaystyle n=n_{0}$ .
2. b)
  
  Suponiendo que el resultado es cierto para un numero natural $\displaystyle n\geq n_{0}$ , demostramos que necesariamente el resultado tambien es cierto para $\displaystyle n+1$ .
Una vez probado esto, habremos demostrado que el resultado es cierto para todo numero natural $\displaystyle n\geq n_{0}$ .
2.
Si queremos probar que una cierta propiedades valida para todo numero entero $\displaystyle n\in\mathbb{Z}$ usando el principio de induccion, debemos seguir los siguientes pasos:
1. a)
  
  Comprobar que el resultado es cierto para $\displaystyle n=0$ .
2. b)
  
  Suponiendo que el resultado es cierto para un numero natural $\displaystyle n$ , demostramos que necesariamente el resultado tambien es cierto para $\displaystyle n+1$ .
3. c)
  
  Suponiendo que el resultado es cierto para un numero entero negativo $\displaystyle n\leq 0$ , demostramos que necesariamente el resultado tambien es cierto para $\displaystyle n-1$ .

Ejemplo.

Demostrar que si $\displaystyle n\in\mathbb{Z}$ entonces $\displaystyle n^{3}-n$ es multiplo de 3.

Demostración.

Lo demostraremos por induccion sobre $\displaystyle n\in\mathbb{Z}$ . Para ello, primero probamos que se cumple para $\displaystyle n=0$ .

\displaystyle n^{3}-n=0^{3}-0=0=3\cdot 0\Rightarrow\text{Es multiplo de 3.}

Ahora, comprobamos que si vale para $\displaystyle n$ entonces tambien vale para $\displaystyle n+1$ .

(n+1)^{3}-(n+1)=n^{3}+3n^{2}+3n+1-n-1=n^{3}-n+3n^{2}+3n\overset{\text{H.I.}}{=% }\\ =3q+3n^{2}+3n=3(q+n^{2}+n)\Rightarrow\text{Es multiplo de 3. }

Por ultimo, demostramos que si es cierto para $\displaystyle n$ entonces tambien lo es para $\displaystyle n-1$ .

(n-1)^{3}-(n-1)=n^{3}-3n^{2}+3n-1-n+1=n^{3}-n-3n^{2}+3n\overset{\text{H.I.}}{=% }\\ =3q-3n^{2}+3n=3(q-n^{2}+n)\Rightarrow\text{Es multiplo de 3.}

Por tanto, por el principio de induccion hemos demostrado que se cumple el teorema para todo $\displaystyle n\in\mathbb{Z}$ . ∎

Existe otra extension que se basa en el siguiente principio que se deduce trivialmente del principio de induccion:

Proposición 4.1 (Principio de induccion completa).

Si $\displaystyle P$ es una cierta propiedad de forma que se cumple simultaneamente:

1.

el numero $\displaystyle n=1$ cumple la propiedad $\displaystyle P$ y
2.

siempre que un cierto numero $\displaystyle n\in\mathbb{N}$ de forma que todos los numeros menores o iguales que el cumple la propiedad $\displaystyle P$ , el siguiente numero tambien cumple la propiedad $\displaystyle P$

entonces todos los numeros naturales cumplen la propiedad $\displaystyle P$ .

Ejemplo.

Vamos a demostrar el teorema fundamental de la aritmetica, que dice que todo numero natural $\displaystyle n>1$ puede expresarse (de forma unica) como producto de potencias de numeros primos, es decir

\displaystyle n=p^{e_{1}}_{1}\cdot p^{e_{2}}_{2}\cdot\ldots\cdot p^{e_{k}}_{k}

donde $\displaystyle k\in\mathbb{N}$ , $\displaystyle p_{1},\ldots,p_{k}$ son numeros primos y $\displaystyle e_{1},\ldots,e_{k}\in\mathbb{N}$ .

Demostración.

Lo demostramos por induccion completa sobre $\displaystyle n$ . Para ello, primero comprobamos que el resultado es cierto para $\displaystyle n=2$ . Como 2 es numero primo, se puede expresar como $\displaystyle 2=2^{1}$ . En segundo lugar, demostramos que si $\displaystyle 1,2,3,\ldots,n$ cumplen la propiedad, entonces $\displaystyle n+1$ cumple la propiedad. Para verlo, hay dos casos:

1.

Si $\displaystyle n+1$ es primo, entonces $\displaystyle n+1=(n+1)^{1}\;(p_{1}=n+1,\,e_{1}=1)$ . Cumple la tesis de induccion.
2.

Si $\displaystyle(n+1)$ no es primo, entonces es divisible por algun numero menor que $\displaystyle n+1$ , luego $\displaystyle n+1=s\cdot t$ con $\displaystyle s,t$ numeros enteros entre 1 y $\displaystyle n$ . Como $\displaystyle s$ y $\displaystyle t$ son numeros enteros entre 1 y $\displaystyle n$ , usando la hipotesis de induccion $\displaystyle s=p^{e_{1}}_{1}\cdot\ldots\cdot p^{e_{k}}_{k}$ y $\displaystyle t=q^{f_{1}}_{1}\cdot\ldots\cdot q^{f_{n}}_{n}$ . Por tanto,

$\displaystyle n+1=s\cdot t=\underbrace{p^{e_{1}}_{1}\cdot\ldots\cdot p^{e_{k}}% _{k}\cdot q^{f_{1}}_{1}\cdot\ldots\cdot q^{f_{n}}_{n}}_{\text{Producto de % potencias de primos}}$

La unicidad está demostrada en 8. ∎

Ejemplo.

Ejercicio 8 - Probar que la suma de los cubos de tres numeros naturales consecutivos es multiplo de 9.

Demostración.

Debemos probar que $\displaystyle n^{3}+(n+1)^{3}+(n+2)^{3}$ es multiplo de 9 para todo $\displaystyle n\in\mathbb{N}$ . Lo demostraremos por induccion sobre $\displaystyle n$ . En primer lugar, comprobamos que es cierto para $\displaystyle n=1$ .

\displaystyle n^{3}+(n+1)^{3}+(n+2)^{3}=1^{3}+2^{3}+3^{3}=1+8+27=36=9\cdot 4

Ahora, demostramos que si es cierto para $\displaystyle n$ es cierto para $\displaystyle n+1$ .

(n+1)^{3}+(n+2)^{3}+(n+3)^{3}=(n+1)^{3}+(n+2)^{3}+(n^{3}+9n^{2}+27n+27)=\\ =n^{3}+(n+1)^{3}+(n+2)^{3}+9n^{2}+27n+27=9k+9n^{2}+27n+27=\\ =\boxed{9(k+n^{2}+3n+3)}

Por el principio de induccion, se cumple para todo $\displaystyle n\in\mathbb{N}$ . ∎