Inducción matemática

Recursión

Antes de presentar la inducción matemática y ver algunos ejemplos, mencionaremos algo acerca de un concepto relacionado: la recursión.

Aunque los dos conceptos que veremos se pueden escribir en un contexto más general, en este momento nos restringimos a los números naturales. Es importante notar que los números naturales son de dos tipos, el cero y los sucesores. Además, estos dos tipos de números son ajenos, es decir, el cero no es sucesor de ningún número natural.

De alguna manera lo anterior sugiere una presentación de los naturales mediante un “elemento distinguido”, \(0\in\mathbb{N}\), y una “función generadora” \(s\colon\mathbb{N}\to\mathbb{N}\) que a cada número natural le asocia su sucesor.

\(0\)	\(1\)	\(2\)	\(3\)	…
\(\quad 0\quad\)	\(\quad s(0)\quad\)	\(\quad s(s(0))\quad\)	\(\quad s(s(s(0)))\quad\)	…

En la tabla se ve un poco el sentido de “elemento distinguido” y “función generadora”.

Dada esta forma de expresar a los naturales para definir una función con dominio \(\mathbb{N}\) se puede definir para \(0\), suponer definido para un número \(n\) y definir para \(s(n)\). Este método de definir funciones se llama recursión. La manera formal de escribir el método es la siguiente.

Teorema (Recursión)

Sean \(A\) un conjunto y \(a\in A\) un elemento y \(f\colon A\to A\) una función. Existe una única función \(h\colon\mathbb{N}\to A\) tal que

1. \(h(0)=a\),
2. \(h(s(n))=f(h(n))\).

Como recursión puede ser un poco abstracta en este momento veremos cómo se usa para definir algunas funciones.

Primero intentaremos definir una función que sume \(n\) a cada número natural. Como sabemos qué queremos obtener daremos una notación espacial para la función deseada, \(+_n\colon\mathbb{N}\to\mathbb{N}\). Además, en este caso sabemos qué debe hacer la función, entonces primero daremos los valores de la función (los puntos 1 y 2 del teorema de recursión) y después veremos cuál es el conjunto, el elemento y la función que necesitamos.

1. \(+_n(0)=n\), (es decir, \(n+0=n\))
2. \(+_n(s(m))=s(+_n(m))\), (es decir, \(n+s(m)=s(n+m)\))

Si recordamos que \(s(n)=n+1\), entonces otra forma de escribir el segundo punto es \(+_n(m+1)=+_n(m)+1\), o bien, \(n+(m+1)=(n+m)+1\).

Como sumar \(n\) a un natural devuelve un natural, entonces el conjunto \(A\) debe ser \(\mathbb{N}\). El elemento \(a\in A\) del teorema es el resultado del primer punto, es decir, \(n\). Finalmente la función \(f\colon A\to A\) es la función que aplicamos al final en el punto 2, es decir, \(s\colon\mathbb{N}\to\mathbb{N}\).

Además hay muchas variantes de recursión que nos permiten definir otras funciones. Por ejemplo, hay una versión donde el dominio de la función que definimos puede tener dos variables. Con esta variante podemos definir por recursión la suma usual \(+\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}\). En otras variante se puede dar un valor a más de un punto, en la versión que presentamos sólo le podemos dar un valor a \(0\) y de ahí el resto queda determinado por la función \(f\). En la versión que mencionamos podríamos dar un valor a \(0\) y a \(1\) y de ahí hacer la recursión. Además, nuestra versión sólo usa el valor de \(h\) en el punto inmediato anterior, como se puede ver en el punto 2 del teorema. También es posible tener versiones de recursión que usen algunos o todos los valores anteriores.

Un ejemplo que use una versión diferente de recursión es la definición de la sucesión de Fibonacci.

1. \(\text{fib}(0)=0\),
2. \(\text{fib}(1)=1\),
3. \(\text{fib}(n+2)=\text{fib}(n+1)+\text{fib}(n)\).

También hay versiones donde la función auxiliar \(f\) puede tener parámetros adicionales. Por ejemplo, si tomamos \(1\in\mathbb{N}\) y \(f\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}\) dada por \(f(n,m)=(n+1)\cdot m\), entonces por recursión podemos definir la función que satisface

1. \(0! = 1\),
2. \((n+1)! = f(n,n!) = (n+1)\cdot n!\).

No se escribieron las versiones de recursión que permiten definir las últimas funciones para evitar escribir cosas que pueden ser complicadas de entender. Sin embargo, lo que sí debe quedar claro es que recursión es un método para definir.

Inducción matemática

Normalmente cuando se define alguna función, lo siguiente es tratar de ver cómo se comporta, es decir, demostrar que satisface ciertas propiedades. Esto nos lleva a la necesidad de un método de demostración. Este método es la inducción matemática.

Con subconjuntos

Si tomamos un subconjunto \(A\subseteq\mathbb{N}\), ¿cómo demostramos que \(A=\mathbb{N}\)? Por lo que sabemos de conjuntos la forma de mostrar la igualdad sería tomar un elemento arbitrario \(n\in\mathbb{N}\) y demostrar que \(n\in A\). Sin embargo, esto no usa la estructura de los números naturales. Para hacer una demostración que haga uso de la estructura de los naturales mostramos que \(0\in A\) y que si \(n\in A\) entonces \(s(n)\in A\). De esta manera tendremos que \(1\in A\), luego \(2\in A\), y así sucesivamente. Con esto podemos concluir que \(A=\mathbb{N}\).

Teorema (Inducción)

Sea \(A\subseteq\mathbb{N}\). Si \(A\) satisface

1. \(0\in A\),
2. \(n\in A\Rightarrow s(n)\in A\), entonces \(A=\mathbb{N}\).

Veamos un ejemplo de cómo se usa la inducción matemática. Sabemos que la suma de los \(n\) primeros números naturales se calcula con la fórmula

\[\begin{equation} \label{eq:sum} \sum_{i=0}^n i = \frac{n(n+1)}{2}. \end{equation}\]

Para demostrar esta fórmula usaremos inducción matemática. Primero formamos el conjunto

\[A = \left\{n\in\mathbb{N}\mid \sum_{i=0}^n i = \frac{n(n+1)}{2}\right\}\]

y queremos demostrar que \(A=\mathbb{N}\). La demostración, siguiendo los puntos 1 y 2 del teorema de inducción, se divide en tres pasos:

Base de la inducción: \(0\in A\),
Por un lado tenemos que \(\sum_{i=0}^0 i = 0\) y por otro lado que \(\frac{0(0+1)}{2}=0\). Por lo que \(0\in A\).

Hipótesis de inducción: Supongamos que \(n\in A\),
Supongamos que \(\sum_{i=0}^n i = \frac{n(n+1)}{2}\).

Paso inductivo: \(n+1\in A\), Queremos demostrar que \(\sum_{i=0}^{s(n)} i = \frac{(n+1)(n+1+1)}{2}\). Lo cual se sigue de la hipótesis de inducción como se muestra a continuación.

\[\begin{align*} \sum_{i=0}^{n+1} i & = \left(\sum_{i=0}^{n} i\right) + (n+1) \\ & = \frac{n(n+1)}{2} + n+1 && \text{por HI} \\ & = \frac{n(n+1)+2(n+1)}{2} \\ & = \frac{(n+1)(n+2)}{2} && \text{factorizando }n+1. \end{align*}\]

De esta manera, el teorema de inducción nos permite concluir \(A=\mathbb{N}\). En otras palabras la fórmula \eqref{eq:sum} es válida para todo \(n\in\mathbb{N}\).

Con fórmulas

Si se observa con cuidado lo que se hizo en el ejemplo anterior, se puede notar que el papel del conjunto \(A\) fue un tanto superfluo. Una forma de deshacernos de la necesidad de un conjunto es considerar una propiedad de los números naturales. En el ejemplo de arriba la propiedad es

\[\varphi(n) \iff \sum_{i=0}^n i = \frac{n(n+1)}{2}.\]

Este enfoque es útil desde el punto de vista que nos permite demostrar cosas usando inducción sin la necesidad de escribir un conjunto. Sin embargo, no todo subconjunto de \(\mathbb{N}\) se puede expresar de esta manera. Aún así, es poco común encontrarse con subconjuntos que no se puedan expresar de esta manera.

Para el resto de la sección fijamos \(\varphi(n)\) una propiedad de números naturales.

De nuevo aprovecharemos que los números naturales “están generados” por el cero y la función sucesor, como en la tabla de arriba. En este caso demostraremos que el cero tiene la propiedad, es decir, \(\varphi(0)\). Luego supondremos que \(n\) tiene la propiedad, es decir, \(\varphi(n)\), y demostraremos que \(s(n)\) también tiene la propiedad, es decir, \(\varphi(s(n))\). Con este proceso podemos afirmar que \(1\) tiene la propiedad, luego \(2\), luego \(3\), y así sucesivamente. De esta manera concluimos que todos los números naturales tienen la propiedad.

Teorema (Inducción)

Si \(\varphi(0)\) y \(\varphi(n)\implies\varphi(s(n))\), entonces \(\varphi(n)\) para todo \(n\in\mathbb{N}\). En una fórmula,

\[\varphi(0)\land \forall n\in\mathbb{N}\;[\varphi(n)\to\varphi(s(n))] \to\forall n\in\mathbb{N}\;\varphi(n).\]

Inducción fuerte

Para terminar esta sección veremos una variante de inducción que tiene muchas aplicaciones. Esta variante no hace explícita la estructura que hemos reconocido y usado en los números naturales.

Teorema (Inducción fuerte)

\[\forall n\in\mathbb{N}\;[(\forall m < n \;\varphi(m))\to\varphi(n)] \to\forall n\in\mathbb{N}\;\varphi(n).\]

Una observación acerca de inducción fuerte es que no se necesita demostrar que un número en particular tiene la propiedad, es decir, la base de inducción esté incluida en la hipótesis de inducción. Por lo tanto, no se debe perder el tiempo haciendo demostraciones que no sirven para nada.

Un ejemplo de cómo se usa inducción fuerte es la demostración de que todo número se puede expresar como producto de primos. La propiedad \(\varphi(n)\) es que \(n\) se puede expresar como producto de primos. De esta forma lo que queremos demostrar es el consecuente del teorema de inducción fuerte. Por lo tanto basta ver que se satisface el antecedente del teorema de inducción fuerte. Para esto tomamos \(n\in\mathbb{N}\).

Hipótesis de inducción: Supongamos que todo número menor que \(n\) se puede expresar como producto de primos.

Paso inductivo: Queremos demostrar que \(n\) se puede expresar como producto de primos. Si \(n\) es primo, entonces ya está expresado como producto de primos. Si no es primo, entonces \(n=ab\) con \(a,b<n\). Por la hipótesis de inducción \(a\) y \(b\) se pueden expresar como producto de primos, entonces \(n\) también se puede expresar como producto de primos.

De esta manera, inducción fuerte nos permite concluir que todo número se puede expresar como producto de primos, como queríamos.

Algo adicional

Un último comentario acerca de lo que vimos en esta sección es que lo que usamos en realidad de los números naturales es que son bien ordenados. De hecho, son equivalentes los dos principios de inducción con el principio de buen orden. Por lo tanto, es posible hacer inducción o inducción fuerte en cualquier conjunto bien ordenado. Por ejemplo, en el conjunto \(\{n\in\mathbb{N}\mid n\geq 4\}\) o en el conjunto \(\{9,10,11,\ldots,57\}\).

Al final la idea de “elementos básicos” y “operaciones generadoras” es lo que está detrás de todo esto. Así, también es posible hacer inducción en los enteros. Habrá que demostrar que un entero, como \(0\), tiene la propiedad. Luego suponer que \(n\) tiene la propiedad y demostrar que \(n+1\) y \(n-1\) también la tienen.