Inducción

Consideremos la siguiente situación: en una fiesta con $n$ invitados, al sonar una campana, cada persona debe aventar un trozo de pastel a la persona más cercana a ella. Si asumimos que todas las distancias son distintas dos a dos, entonces demuestra que si $n$ es impar, al menos una persona no será embarrada de pastel.

Este curso inicia con inducción matemática. Recordemos que el conjunto de los números naturales $\mathbb{N}$ es definido como

(1)
\begin{align} \mathbb{N}=\left\{ \text{enteros} : n \geq 0 \right\} \end{align}

esto es, $\mathbb{N}$ es en conjunto de los enteros no negativos. Notemos que algunos autores consideran al conjunto de los números naturales a partir del uno (todo depende de la construcción que se haga de los números naturales) y hacerlo así no genera ningún problema en esta teoría, tan solo hay que hacer las adecuaciones necearías en algunos enunciados.

La inducción matemática es posiblemente la técnica para hacer demostraciones más divertida. Está basada en la siguiente propiedad fundamental (axioma) de $\mathbb{N}$:

El principio del buen orden (PBO) : Todo subconjunto no vacío $C\subset \mathbb{N}$ tiene un primer elemento respecto al orden usual de los números enteros. Por primer elemento nos referimos a un elemento $c\in C$ tal que $c\le x$ para todo $x\in C$.

Notemos que este axioma es de hecho intuitivamente obviamente verdadero. La razón por la que la establecemos como axioma es porque cuando se desarrolla la teoría de conjuntos de manera formal, a partir de axiomas fundamentales, el principio anterior no se sigue de axiomas más simples y de hecho tiene que ser incluido como un axioma (o alguno de sus equivalentes).

Notar por ejemplo que el conjunto de los números racionales $\mathbb{Q}$ no satisface este principio.

Una consecuencia del principio del buen orden nos dice que cualquier subconjunto de números enteros que sean mayores o iguales que un entero fijo $m$ (que puede ser negativo) tiene un primer elemento. En efecto si $m \ge 0$ entonces este es el principio del buen orden. Si $m<0$ entonces tenemos que si $A$ es un tal conjunto, este puede ser escrito como:

(2)
\begin{align} A = (A \cap \left\{ m, m+1, \ldots -1 \right\} \cup C\cap \mathbb{N}) \end{align}

Si $(A \cap \left\{ m, m+1, \ldots -1 \right\}\ne \emptyset$ entonces este conjunto es finito y por lo tanto tiene un elemento menor, que será obviamente el elemento menor en $A$. Si por el contrario $(A \cap \left\{ m, m+1, \ldots -1 \right\} = \emptyset$ entonces $C\subset \mathbb{N}$ y el principio del buen orden implica que este conjunto tiene un primer elemento.

En el argumento anterior, se utilizó que cualquier conjunto finito de números enteros (no necesariamente positivos) tiene siempre un primer elemento. Este hecho aunque (también) obvio, requiere de un argumento basado en el principio del buen orden.

La primera aplicación de este resultado nos dice que todo entero positivo distinto de 1, es producto de números primos.

Definición: Un número natural $p$ es primo si $p>1$ y no existe una factorización $p=ab$ con $a<p \text{ y } b<p$ números naturales.

Proposición: Todo entero $n\ge 2$ es primo o producto de primos.

Demostración: Sea $A$ el subconjunto de los naturales formado por todos aquellos enteros $n\ge 2$ para los que la proposición es falsa, es decir que ni son primos ni producto de primos. Si $A=\emptyset$ entonces no hay nada por hacer, de lo contrario, como $A\subset \mathbb{N}$ entonces este conjunto debe tener un primer elemento, digamos $n$, com $n$ no es primo, entonces se tiene que existen naturales $a,b$ tal que $n =ab$ con $a,b<n$. Ninguno de $a$ o $b$ son elementos de $A$ pues son más pequeños que el menor elemento $n$ de $A$, por lo tanto tanto $a$ como $b$ o son primos o son producto de primos y por lo tanto $n$ es producto de (al menos dos) primos, pero entonces $n\notin A$ lo cuál no es posible por hipótesis, esto demuestra que entonces la única opción viable es que $A=\emptyset$ y la proposición se sigue.

El principio de Inducción matemática (PIM): Sea $S(n)$ una familia de proposiciones, una para cada natural $n\ge m$ en donde $m$ denota un entero cualquiera pero fijo. Si

  1. $S(m)$ es verdadera y
  2. $S(k)$ es verdadera implica $S(k+1)$ es verdadera

entonces $s(n)$ es verdadera para todo entero $n\ge m$.

Una imagen mental que nos podemos hacer del principio de inducción es la de unas escaleras. El primer peldaño está marcado con $m$ y los subsecuentes peldaños más altos con $m+1, m+2,\ldots$ sabemos que podemos llegar al primer peldaño, si además sabemos que si llegamos a cierto peldaño, digamos al $n$, entonces podemos llegar al siguiente $n+1$ concluimos entonces que podemos llegar a todos los peldaños.

Ejemplo: Probar que para cada entero positivo $n$, tenemos:

(3)
\begin{align} 1+2+\cdots+n= \frac{n(n+1)}{2} \end{align}

Indicar claramente quién es $S(n)$, quién es el primer elemento (la base de la inducción).

Ejemplo: Demuestra que $1+q+\cdots + q^n = \frac{1-q^{n+1}}{1-q}$.

El principio de inducción es equivalente al siguiente entunicado:

Principio de Inducción (modificado): Supongamos que $B\subset \mathbb{N}$ es un subconjunto de los naturales tal que:

  1. $0\in B$
  2. si $n\in B$ entonces $n+1\in B$

entonces $B=\mathbb{N}$.

El principio del buen orden es también equivalente al principio de inducción matemática. En efecto si suponemos el principio del buen oren entonces sea $A$ el conjunto de enteros $n\ge m$ para los que $S(n)$ es falsa. Si $A=\emptyset$ entonces hemos terminado. De lo contrario, existe un primer elemento $k\in A$. Este elemento tiene que ser mayor estrictamente que $m$ pues $s(m)$ es verdadera por la hipótesis de inducción 1. Esto quiere decir que $S(k-1)$ es una proposición en la familia y como $k-1\ne A$ tenemos que $S(k-1)$ es verdadera. Pero por la hipótesis de inducción 2, tenemos que entonces $S(k)=S((k-1)+1)$ es verdeara, contradiciendo que $k\in A$ o bien que $s(k)$ es falsa.

Ejercicio: Probar que el principio de inducción implica al principio del buen orden.

Inducción fuerte: Sea $S(n)$ una familia de proposiciones, una para cada entero $n\ge m$ para algún entero fijo $m$. Si

  1. $S(m)$ es verdadera
  2. Si $S(k)$ es verdadera para todo $m\ge k< n$ entonces $S(n)$ es verdadera para para todos los enteros $n\ge m$.

Ejercicio: Demuestra que ambos principios de inducción son equivalentes (y por lo tanto equivalente al principio del buen orden).

Teorema (Propiedad Arquimediana). Si $a,b$ son enteros postivios, entonces existe un entero positivo $n$ tal que $na\ge b$.

Demostración: Asumamos que el enunciado es falso, entonces para algunos enteros $a,b$ pasa que $na<b$ para cada entero positivo $n$. Entonces el conjunto

(4)
\begin{align} S=\left\{ b-na: n \text{ es un entero positivo } \right\} \end{align}

está formado enteramente de números positivos. Por el principio del buen orden, existe un entero positivo $m$ tal que $b-ma$ es primer elemento de $S$. Pero $b-(m+1)a \in S$ pues $S$ contiene a todos los enteros de esta forma. Más aún teneos que

(5)
\begin{equation} b-(m+1)a= (b-ma)-a < b-ma, \end{equation}

contradiciendo la elección de $b-ma$ como el primer elemento en $S$. Esta contradicción se debe a haber supuesto que la propiedad Arquimediana no se satisface, por lo tanto esta propiedad es verdadera.

La Inducción matemática es usada frecuentemente como un método para hacer definiciones recurrentes. Por ejemplo el símbolo $n!$ el factorial de $n$ puede ser definido como:

  • 0!=1
  • n! = n(n-1)! para $n > 0$.

Estas dos condicines nos dan una regla para darle un sentido a $n!$ para cada entero no negativo. Así 1! =1; 2! = 2\cdot 1! = 2 etc.
Inducción se aplica para mostrar que $n!$, como una funcíon en los naturales, existe y es única.

Ejercicio: Usa inducción para demostrar que $n!$ está bien definido para todo natural y que cualquier funcíon en los naturales $f:\mathbb{N}\to \mathbb{N}$ que satisfaga $f(0)=1$ y que $f(n+1)= f(n)$ implica que $f(n) = n!$.

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License