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

Example 4.1.

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

Proof 4.2.

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

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

Ahora, comprobamos que si vale para $n$ entonces tambien vale para $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 $n$ entonces tambien lo es para $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 $n\in\mathbb{Z}$ .

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

Proposition 4.3 (Principio de induccion completa).

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

1.

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

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

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

Example 4.4.

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

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

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

Proof 4.5.

Lo demostramos por induccion completa sobre $n$ . Para ello, primero comprobamos que el resultado es cierto para $n=2$ .

Como 2 es numero primo, se puede expresar como $2=2^{1}$ .

En segundo lugar, demostramos que si $1,2,3,\ldots,n$ cumplen la propiedad, entonces $n+1$ cumple la propiedad. Para verlo, hay dos casos:

1.

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

Si $(n+1)$ no es primo, entonces es divisible por algun numero menor que $n+1$ , luego $n+1=s\cdot t$ con $s,t$ numeros enteros entre 1 y $n$ .

Como $s$ y $t$ son numeros enteros entre 1 y $n$ , usando la hipotesis de induccion $s=p^{e_{1}}_{1}\cdot\ldots\cdot p^{e_{k}}_{k}$ y $t=q^{f_{1}}_{1}\cdot\ldots\cdot q^{f_{n}}_{n}$ . Por tanto,

$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.20.

Example 4.6.

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

Proof 4.7.

Debemos probar que $n^{3}+(n+1)^{3}+(n+2)^{3}$ es multiplo de 9 para todo $n\in\mathbb{N}$ . Lo demostraremos por induccion sobre $n$ .

En primer lugar, comprobamos que es cierto para $n=1$ .

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 $n$ es cierto para $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 $n\in\mathbb{N}$ .