Lógica/El principio de inducción

Ortografía

Esta página o sección necesita una revisión de ortografía y gramática.
Puedes ayudar editándolo

El principio de inducción

Dicho principio establece que para un conjunto determinado de números, ó elementos, si se prueba que determinada propiedad, o proposición es valida para el primer elemento del conjunto, y a su vez, tomando como hipotesis que es valido para "k" elemento siendo k un número natural, también probamos que se cumple para "k+1" siendo k+1 el inmediato siguiente de k, entonces esa propiedad o afirmación se cumple para todos los elementos del conjunto analizado. Necesariamente podemos inferir que si se prueba que determinada proposición o elemento es válido para el primer enunciado de un conjunto (premisa), esa afirmación se cumplirá para todos los elementos consecutivos, valga la redundancia, del conjunto analizado (razonamiento).

Imaginemos que una de estas filas de fichas de dominó se extendiese hasta más allá de lo que alcanza la vista, y supongamos que sabemos que estos dos enunciados son verdad:

Enunciado 1: Alguien ha tirado la primera ficha.,
Enunciado 2: Si una ficha es derribada, entonces ésta tira la siguiente.

De 1 y 2 podemos concluir que todas las fichas acabarán cayendo. ¿Por qué? La respuesta es que, en primer lugar, sabemos que la primera ha caído por el enunciado 1. Sabemos también (por el segundo enunciado) que si la primera ficha cae, entonces derriba la segunda, así que ésta tendrá que caer. Y si la segunda ficha cae, entonces derriba la tercera (por el enunciado 2)... y así sucesivamente. Si alguien nos preguntase si la séptima (o la vigésima, o la milésima) iba a ser derribada, podríamos responder que sí, que la cadena de derribos se aproxima a ella inexorablemente y que la acabará tirando. Esto nos lleva a la afirmación del siguiente principio:

Principio de las fichas de dominó: En una fila de fichas de dominó en la que son verdad los enunciados 1 y 2, todas las fichas son finalmente derribadas.

Este principio, que puede parecer trivial, es sin embargo interesante porque es un caso particular del principio de inducción, que nos encontraremos más adelante y que nos servirá como arma para hacer algunas demostraciones importantes.

La suma de Gauss^*

Corría el año 1789. Carl Friedrich Gauss, que algún día llegaría a ser un gran matemático y físico, tenía sólo nueve años. Cierta mañana, su profesor, que quería mantener ocupados a los niños durante un rato, les mandó sumar los cien primeros números. Apenas había terminado de asignar la tarea cuando Gauss se levantó y entregó su pizarra. Sobre la pizarra había un único número: 5050. Resultó que 5050 era precisamente la suma de los números desde uno hasta cien. ¿Cómo había encontrado la solución tan rápido? (Intenta resolverlo antes de continuar).

Gauss se dio cuenta de algo curioso. La suma que había que hacer era $1+2+3+\ldots +98+99+100$ , que puede llevar bastante tiempo si se hace en ese orden, pero si se suman el primero y el último número, se obtiene $101$ . Lo mismo ocurre si se suma el segundo con el penúltimo y el tercero con el antepenúltimo, y así sucesivamente. Se puede ver que todas esas sumas tienen el mismo resultado.

{\begin{matrix}1+100=101\\2+99=101\\3+98=101\\\vdots \\49+52=101\\50+51=101\end{matrix}}

Puesto que hay evidentemente 50 parejas cuya suma es 101, el resultado de la suma desde uno hasta cien es $50\times 101=5050$ . Esta manera de enfrentarse al problema es un excelente ejemplo de solución elegante.

Esta solución no sólo vale para los números de uno a cien. En general, la suma de los $n$ primeros números (siendo $n$ un número par) es el último número más uno por el número de parejas, es decir $\left(n+1\right)\times {\frac {n}{2}}$ .

Preguntas

¿Es válida esta fórmula si $n$ es un número impar?

Si. Aunque la formula se divida entre dos, el numerador siempre sera par: si n es impar, entonces (n+1) es par, si (n+1) es impar, entonces n es par, por tanto su producto siempre sera par y el resultado de la formula siempre sera un entero positivo.

¿Cómo sería la fórmula para sumar una serie de números consecutivos que no empezara en el uno?

Esto lo expresamos como $Sumatoria$ desde K=(numero inicial) hasta el numero a sumar

Principio de inducción para números naturales

La teoría de números, una disciplina de las matemáticas, se dedica especialmente a estudiar las propiedades de los números naturales.¹ Las propiedades se pueden enunciar en muchos casos de manera sencilla, por ejemplo, "todo número par está entre dos números impares" o "existen infinitos números primos de la forma $n!+1$ ". Puesto que hay infinitos números naturales, no se puede ir comprobando caso por caso que, digamos, ningún número impar es divisible por dos. Hacen falta estrategias que demuestren de golpe todos los casos. Algunas de estas estrategias hacen uso del principio de inducción.

Supongamos que nos preguntemos si todos los números naturales tienen una propiedad que llamaremos ${\mathcal {P}}$ , de la que sabemos dos cosas:

Enunciado 1: El número uno posee la propiedad ${\mathcal {P}}$ .²
Enunciado 2: Si un número posee la propiedad ${\mathcal {P}}$ , el siguiente número también la posee. Es decir, si $n$ tiene la propiedad ${\mathcal {P}}$ , entonces $n+1$ también.

Se puede ver el parecido entre estas dos afirmaciones y las que vimos para las fichas de dominó, más arriba. De manera análoga, podremos enunciar para los números naturales un principio parecido al principio de las fichas de dominó.

Principio de inducción: Si los enunciados 1 y 2 son verdaderos, entonces todos los números naturales tienen la propiedad ${\mathcal {P}}$ .

La idea que hay detrás de los dos principios es muy parecida. En este caso cada número le "comunica" al siguiente la propiedad (según el enunciado 2) por lo que, si el primero tiene la propiedad, la acaban teniendo todos.

Hasta aquí todo suena fácil. La gracia está en que normalmente no sabemos que, para una cierta propiedad, se cumplen los enunciados 1 y 2, con lo cual no sabemos si el principio de inducción tiene algo que ver con ella. Pero, si conseguimos demostrar que los dos enunciados se cumplen para la propiedad, entonces sabremos que todos los números naturales la tienen.

Por ejemplo, para cualquier número natural $n$ , la suma de todos los números desde 1 hasta $n$ es

$1+2+3+\ldots +n={\frac {\left(n+1\right)\times n}{2}}$

Para demostrar que esto es verdad para cualquier número natural, basta con demostrar que para esta propiedad (que llamaremos ${\mathcal {P}}$ ³) los enunciados 1 y 2 son verdad. El primer enunciado se cumple, ya que la suma desde 1 hasta 1 es simplemente 1, que es lo que se obtiene de la fórmula. En efecto, sustituyendo en la fórmula anterior $n=1$ obtenemos

${\frac {\left(1+1\right)\times 1}{2}}={\frac {2}{2}}=1$

Así que sabemos que el enunciado 1 se cumple. El segundo enunciado parece más complicado porque suena mucho más abstracto. No se trata de demostrar que un número posee la propiedad ni que la posee el siguiente, sino que si un número posee la propiedad entonces la posee el siguiente ¿Cómo se hace esto?

Supongamos que la propiedad se cumple para un cierto número $n$ . Entonces es verdad que para este número

$1+2+3+\ldots +n={\frac {\left(n+1\right)\times n}{2}}$

Por lo tanto, la suma desde 1 hasta el número siguiente será

$1+2+3+\ldots +n+(n+1)={\frac {\left(n+1\right)\times n}{2}}+\left(n+1\right)$

Si ahora operamos un poco con el miembro de la derecha, podemos obtener una expresión que resultará interesante un poco más adelante.

${\begin{matrix}{\frac {\left(n+1\right)\times n}{2}}+\left(n+1\right)&=&{\frac {\left(n+1\right)\times n}{2}}+{\frac {2\times \left(n+1\right)}{2}}={\frac {\left(\left(n+1\right)\times n\right)+\left(2\times \left(n+1\right)\right)}{2}}=\\&=&{\frac {n^{2}+n+2n+2}{2}}={\frac {\left(n+2\right)\times \left(n+1\right)}{2}}={\frac {\left(\left(n+1\right)+1\right)\times \left(n+1\right)}{2}}\end{matrix}}$

Hasta ahora, según parece, sólo hemos hecho algo de aritmética. Detengámonos a pensar. Si la propiedad ${\mathcal {P}}$ se cumpliese para $n+1$ , entonces habría una fórmula para hallar la suma desde 1 hasta $n+1$ . Esta fórmula se obtendría sustituyendo $n$ por $n+1$ en la fórmula de la suma de Gauss:

$1+2+3+\ldots +\left(n+1\right)={\frac {\left(\left(n+1\right)+1\right)\times \left(n+1\right)}{2}}$

Sorprendentemente, el segundo miembro de esta expresión es igual a la que obtuvimos después de todas nuestras manipulaciones aritméticas. Pero, ¿de dónde sacamos aquella expresión? La obtuvimos suponiendo que el número $n$ tenía la propiedad ${\mathcal {P}}$ , es decir, que se podían sumar todos los números desde 1 hasta $n$ mediante la fórmula que vimos. Por lo tanto, si la fórmula se cumple para $n$ , entonces también se cumple para $n+1$ (sea lo que sea $n$ ). Con esto hemos probado que se cumple el segundo enunciado.

En resumen, preguntándonos qué números tienen la propiedad de que la suma desde 1 hasta ellos es igual a ${\frac {\left(n+1\right)\times n}{2}}$ , hemos llegado a la conclusión de que la propiedad cumple los enunciados 1 y 2. Así que, gracias al principio de inducción, podemos afirmar que todos los números naturales tienen esta propiedad.

Ejercicios

Demostrar que para cualquier número natural $n$ se cumplen las siguientes propiedades:
- $1^{2}+2^{2}+3^{2}+\ldots +n^{2}={\frac {n\times \left(n+1\right)\times \left(2n+1\right)}{6}}$
- $1^{3}+2^{3}+3^{3}+\ldots +n^{3}=\left(1+2+3+\ldots +n\right)^{2}$
Demostrar que en toda fila de hombres y mujeres en la que la primera persona es mujer y la última hombre siempre hay una mujer delante de un hombre en al menos un punto de la fila.

Inducción e inferencia inductiva

Ya comentamos en la introducción que se llama inferencia inductiva (o inducción) al proceso de obtener leyes generales basadas en la observación de casos particulares. ¿Qué relación hay entre la inferencia inductiva y el principio de inducción? Ambas extraen como conclusión una ley o propiedad general a partir de la comprobación de la verdad de ésta en casos particulares. Ahora bien, el principio de inducción garantiza que la propiedad considerada se cumple absolutamente en todos los casos particulares, luego la validez de la conclusión está garantizada deductivamente. Sin embargo, la mayoría de los argumentos inductivos simplemente comprueban que se cumple una propiedad sin considerar todos los casos posibles (normalmente no se conocen todos los casos; incluso hay problemas en los que el número de casos es infinito), y no existe un equivalente de nuestro enunciado 2 que impida que otro caso nuevo contradiga nuestra hipótesis, por lo que no se puede garantizar lógicamente la verdad de la conclusión y se debe considerar como verdadera sólo provisionalmente.

Pregunta

¿Es válido el siguiente argumento?

Al levantarme cierta mañana, pude presenciar un espectacular amanecer. Deseé que todas las mañanas fueran como esa. Desde entonces, siempre me he despertado temprano para ver la salida del Sol, y he observado cómo cada nuevo amanecer sigue al anterior. De esta experiencia podemos concluir, por inducción, que el Sol saldrá mañana y que continuará saliendo en cada jornada sucesiva.

Notas

^* Los detalles de esta historia han sido extraídos de Cooper, D. y Clancy, M.: Oh! Pascal! An Introduction to Programming, W. W. Norton & Company (1982), pp. 61-62.
¹ Los números naturales son los conocidos 1, 2, 3, 4, etc. que se utilizan para contar. El convenio moderno incluye también el cero en el conjunto de los números naturales. Para cualquier número natural (llamémoslo $n$ ) existe el número siguiente $\left(n+1\right)$ .
.pero no siempre es verdad ² Si se incluye el cero en el conjunto de los números naturales, este enunciado enunciado debe ser modificado a
Enunciado 1*: El número cero posee la propiedad ${\mathcal {P}}$ .
Todas las propiedades de los números naturales que se estudian en este artículo valen tanto si se incluye el cero como si no se incluye.
³ La propiedad consiste pues, para un número $n$ , en que la suma desde 1 hasta ese número $n$ es igual a ${\frac {\left(n+1\right)\times n}{2}}$ .
---- <Índice