1.8 Principio de Inducción

Consideremos el siguiente:

El principio anterior es obvio ya que al ser verdadero \(\mathrm{Enu}_{1}\) podemos inferir por la segunda propiedad que \(\mathrm{Enu}_{2}\) lo es pero esto a su ves nos dice que \(\mathrm{Enu}_{3}\) es verdadero, y así sucesivamente.

El Principio de Inducción da lugar a la siguiente regla la cual es extremadamente útil para realizar demostraciones en matemática.

Por supuesto, la Regla de Inducción es (como buena regla) netamente mecánico-operativa y nos dice como operar para probar infinitos enunciados cumpliendo dos tareas concretas. El Principio de Inducción justifica la corrección de esta regla. En algún sentido el Principio de Inducción es mas puro o primitivo ya que solo describe una situación acerca de los valores de verdad de los enunciados, bajo la cual todos resultan verdaderos. La Regla de Inducción se basa en este principio para decirnos que si hacemos ciertas demostraciones, entonces podemos concluir que hemos demostrado todos los enunciados \(\mathrm{Enu}_{n}\). Pero si esto le parece muy filosófico, tiene razón y siga leyendo que lo que viene es mas concreto y útil!

Veamos un ejemplo. Para cada \(n\in\mathbf{N}\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{n}:\) \(1+2+...+n=\frac{n.(n+1)}{2}\)

Nótese que

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{1}:\) \(1=\frac{1.(1+1)}{2}\)

  2. adhocprefixadhocsufix \(\mathrm{Enu}_{2}:\) \(1+2=\frac{2.(2+1)}{2}\)

  3. adhocprefixadhocsufix \(\mathrm{Enu}_{3}:\) \(1+2+3=\frac{3.(3+1)}{2}\), etc.

Es fácil corroborar que alguno en particular es verdadero, simplemente hay que computar y ver si se da la igualdad. Pero por mas que corroboremos un millón de enunciados, no podremos garantizar la veracidad de todos, si no hacemos algún tipo de razonamiento genérico. Justamente la Regla de Inducción nos dice que cosas tenemos que probar para garantizar que todos los enunciados sean verdaderos. Hagamos entonces las pruebas encomendadas por la regla.

  1. adhocprefixadhocsufix Prueba de \(\mathrm{Enu}_{1}\): Note que \[\frac{1.(1+1)}{2}=\frac{1.2}{2}=\frac{2}{2}=1\] por lo cual \(1=\frac{1.(1+1)}{2}\).

  2. adhocprefixadhocsufix Prueba de que para cada \(n\in\mathbf{N}\), se tiene que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es: Sea entonces un \(n_{0}\in\mathbf{N}\) fijo y supongamos que \(\mathrm{Enu}_{n_{0}}\) es verdadero. Probaremos que \(\mathrm{Enu}_{n_{0}+1}\) lo es. Tenemos entonces que \[1+2+...+n_{0}=\frac{n_{0}.(n_{0}+1)}{2}\] por lo cual \[1+2+...+n_{0}+(n_{0}+1)=\frac{n_{0}.(n_{0}+1)}{2}+(n_{0}+1)\] Pero \[\frac{n_{0}.(n_{0}+1)}{2}+(n_{0}+1)=\frac{n_{0}.(n_{0}+1)+2.(n_{0}+1)}{2}=\frac{(n_{0}+2).(n_{0}+1)}{2}=\frac{(n_{0}+1).(n_{0}+2)}{2}\] lo que nos dice que \[1+2+...+n_{0}+(n_{0}+1)=\frac{(n_{0}+1).((n_{0}+1)+1)}{2}\] que es justo lo que afirma \(\mathrm{Enu}_{n_{0}+1}\). Ya que \(n_{0}\) era arbitrario la implicación vale para cada \(n\in\mathbf{N}\).

1.8.1 Variaciones del Principio de Inducción

Nada cambia si la sucesión de enunciados en lugar de comenzar desde \(1\), lo hace desde el \(0\). Es decir

Este caso será muy usado tanto para la parte de computabilidad como para la parte de lógica.

También la sucesión de enunciados puede comenzar desde \(4\), por ejemplo la regla quedaría:

Por ejemplo para cada \(n\geq4\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{n}:\) \(n!>2^{n}\)

O sea

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{4}:\) \(4!>2^{4}\)

  2. adhocprefixadhocsufix \(\mathrm{Enu}_{5}:\) \(5!>2^{5}\)

  3. adhocprefixadhocsufix \(\mathrm{Enu}_{6}:\) \(6!>2^{6}\), etc.

Dejamos al lector la prueba de que \(\mathrm{Enu}_{4},\mathrm{Enu}_{5},\mathrm{Enu}_{6},\mathrm{Enu}_{7},...\) son verdaderos usando la Regla de Inducción desde \(4\).

Nótese que para \(n<4\) no es cierto el enunciado \(n!>2^{n}\) por lo cual la Regla de Inducción desde \(4\) nos viene justo para este caso. Obviamente en otros casos en lugar de \(4\) nos será útil otro elemento de \(\omega\). Enunciamos entonces la regla en forma mas gral:

1.8.2 Inducción Completa

Consideremos la siguiente:

El lector no tendrá inconvenientes en comprender la validez de esta regla. Hay casos en los cuales la Regla de Inducción desde \(n_{0}\) no nos es útil ya que de saber que es cierto \(\mathrm{Enu}_{n}\) no se nos ocurre como probar \(\mathrm{Enu}_{n+1}\), pero si asumimos que \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{n_{0},...,n\}\) entonces si se nos ocurre como probar \(\mathrm{Enu}_{n+1}\). En estos casos es natural aplicar la Regla de Inducción Completa desde \(n_{0}\). Veamos un ejemplo.

Para cada \(n\geq2\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{n}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(n=p_{1}.p_{2}.....p_{k}\)

O sea

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{2}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(2=p_{1}.p_{2}.....p_{k}\)

  2. adhocprefixadhocsufix \(\mathrm{Enu}_{3}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(3=p_{1}.p_{2}.....p_{k}\)

  3. adhocprefixadhocsufix \(\mathrm{Enu}_{4}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(4=p_{1}.p_{2}.....p_{k}\)

etc. Para probar que \[\mathrm{Enu}_{2},\mathrm{Enu}_{3},\mathrm{Enu}_{4},...\] son verdaderos, hagamos las pruebas encomendadas por la Regla de Inducción Completa desde 2.

  1. adhocprefixadhocsufix Prueba de \(\mathrm{Enu}_{2}\): Podemos tomar \(k=1\) y \(p_{1}=2\)

  2. adhocprefixadhocsufix Prueba de que para cada \(n\geq2\), si \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{2,...,n\}\), entonces \(\mathrm{Enu}_{n+1}\) lo es: Sea entonces \(n\geq2\) fijo y supongamos que \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{2,...,n\}\). Probaremos que \(\mathrm{Enu}_{n+1}\) lo es. Si \(n+1\) es primo, entonces podemos tomar \(k=1\) y \(p_{1}=n+1\) para concluir que \(\mathrm{Enu}_{n+1}\) es cierto. Supongamos entonces que \(n+1\) no es primo. Entonces hay \(a,b\) tales que \(n+1=a.b\) y \(a,b\geq2\). Nótese que entonces \(a,b\leq n\). Por hipótesis tenemos que entonces \(\mathrm{Enu}_{a}\) y \(\mathrm{Enu}_{b}\) son ciertos por lo cual existen primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(a=p_{1}.....p_{k}\) y existen primos \(q_{1},...,q_{m}\), con \(m\geq1\) tales que \(b=q_{1}.....q_{m}\). Tenemos entonces que \[n+1=p_{1}.....p_{k}.q_{1}.....q_{m}\] de lo cual claramente obtenemos que \(\mathrm{Enu}_{n+1}\) es verdadero.

Dejamos al lector que experimente un rato la dificultad de intentar usar la Regla de Inducción desde 2 para este caso.

1.8.3 El caso en que la sucesión de enunciados es finita

Algunas veces la sucesión de los enunciados \(\mathrm{Enu}_{n}\) es finita y esto no afecta para nada la idea de la inducción descripta anteriormente. Ya que es muy natural sólo enunciaremos las dos reglas que corresponden a este caso finito.

1.8.4 El principio de inducción usado en la ficción de una prueba

Casi siempre que en matemática probamos algún enunciado, nuestro argumento involucra cierta ficción. Es decir en general, los enunciados matemáticos tienen hipótesis las cuales suponen que ciertos objetos cumplen ciertas propiedades y tienen su conclusión o tesis que es justamente lo que el enunciado asegura debe suceder si se dan las hipótesis. Esto hace que en la prueba se comience suponiendo que se dan las hipótesis y luego se empiece a desarrollar una ficción dentro de la cual vía cierto desarrollo se llegará a la conclusión (que también es parte de esa ficción). Por ejemplo consideremos el siguiente famoso enunciado:

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{1}\): Supongamos \(p\) es un polinomio a coeficientes complejos de grado mayor que \(0\). Entonces \(p\) tiene al menos una raíz compleja, es decir hay un número complejo \(c\) tal que \(p(c)=0\).

En la prueba del mismo asumiremos que \(p\) es un polinomio a coeficientes complejos de grado mayor que \(0\). Este sera el actor inicial de nuestra demostración (película) la cual nos terminara convenciendo de que hay un número complejo \(c\) tal que \(p(c)=0\). Para dar otro ejemplo, consideremos el enunciado:

  1. adhocprefixadhocsufix \(\mathrm{Enu}_{2}\): Sean \(f,g\) funciones. Supongamos \(f\circ g\neq\emptyset\). Entonces \(I_{g}\cap D_{f}\neq\emptyset\).

En la prueba asumiremos que \(f,g\) son funciones y que \(f\circ g\neq\emptyset\). Ellas serán los actores iniciales de nuestra (ficción) demostración, la cual nos terminará convenciendo que \(I_{g}\cap D_{f}\neq\emptyset\).

Pero debemos notar que a lo largo de una demostración pueden surgir nuevos actores en escena. Es muy común que en el medio de una demostración probemos que existe al menos un objeto con cierta propiedad y que inmediatamente digamos sea \(e\) uno de tales objetos, fijado para el resto de nuestra demostración. Claramente \(e\) es un nuevo actor en la ficción de nuestra prueba (película). Para dar otro ejemplo, dentro de una demostración puede suceder que probemos que cierto objeto \(r\) es un número racional. Obviamente \(r\) ya era un actor dentro de la ficción de la prueba, pero ahora podemos incorporar dos nuevos actores \(a,b\in\mathbf{Z}\)tales que \(r=a/b\). Y nuestro argumento (película) sigue ahora con dos nuevos actores. Por ejemplo en la prueba de \(\mathrm{Enu}_{2}\), la cual puede verse aqui, aparte de los actores \(f\) y \(g\) surge el nuevo actor \(e\) tal que \(e\in D_{g}\) y \(g(e)\in D_{f}\), el cual sirve para concluir que \(I_{g}\cap D_{f}\neq\emptyset\).

Resumiendo, en una prueba, aparte de los objetos reales de la matemática, pueden estar involucrados objetos que son solo parte de la ficción correspondiente al argumento de la prueba. Cabe destacar que parte de la madurez de un matemático profesional consiste en tratar e imaginar a dichos objetos como si fueran reales y concretos. Muchas veces en el transcurso de una prueba, se usará alguna versión de la Regla de Inducción aplicada a una sucesión de enunciados que involucran objetos que sólo existen en la ficción de la prueba misma y no fuera de ella.

Esto no trae inconvenientes dado que aún dentro de la ficción de una prueba los conceptos de verdad y de demostración tienen las propiedades que hacen válidos al Principio de Inducción y a la Regla de Inducción, en todas sus versiones.