Inducción matemática

La inducción matemática es un método de demostración muy utilizado en matemáticas, sobre todo cuando trabajamos con números naturales o con alguna otra sucesión.

Principio

El principio básico consiste en demostrar el enunciado para un primer elemento; en los números naturales suele ser n = 1. Esto lo demostramos simplemente sustituyendo. En el siguiente paso, el paso inductivo, demostramos la implicación «si el enunciado se cumple para n = a, entonces se cumple también para n = a + 1».

De estos dos pasos podemos deducir que la expresión dada se cumple para todo n (de algún conjunto con el que estemos trabajando). ¿Por qué es así? Al principio demostramos que la expresión se cumple para n = 1. A la vez sabemos que, si la expresión se cumple para n = a, se cumple también para n = a + 1. Elegimos entonces a = 1. Sabemos que para a = 1 la expresión se cumple y también sabemos que se cumple para a + 1 = 2. En este momento sabemos que la expresión se cumple para a = 2. Pero como se cumple también para a + 1, tiene que cumplirse para 2 + 1 = 3. Y así sucesivamente.

Primer ejemplo

El primer ejemplo será trivial. Demostraremos que, si a un número par cualquiera le sumamos dos, obtenemos de nuevo un número par. Como nos movemos en los números naturales, escribimos un número par en general como 2n, donde n es un número natural. Si sustituimos n por cualquier número natural, obtenemos como resultado un número par; eso se ve a primera vista. La divisibilidad se escribe con una barra vertical así:

$$2\mid 2n$$

Esta notación significa que el dos divide exactamente a la expresión 2n. Ahora que sabemos escribir la divisibilidad, podemos escribir también lo que tenemos que demostrar por inducción matemática.

$$2\mid 2n+2;n\in \mathbb{N}$$

Esto es lo que tenemos que demostrar en el primer ejemplo, es decir, que el dos divide a la expresión 2n + 2; corresponde exactamente al enunciado original en palabras «si a un número par cualquiera le sumamos dos, obtenemos de nuevo un número par».

En el caso base de la inducción lo demostramos para el primer elemento, para el uno. Sustituimos n = 1 en la expresión:

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

El dos divide exactamente al cuatro, así que para el primer elemento se cumple. A continuación llega el paso inductivo, en el que tenemos que demostrar que, si se cumple para el elemento a-ésimo, entonces se cumple también para el elemento (a + 1)-ésimo. Al principio suponemos que se cumple nuestra hipótesis, es decir, n = a:

$$2\mid 2a+2$$

Suponemos que esta expresión es verdadera y la usaremos al construir la demostración. Ahora queremos demostrar que

$$2\mid 2(a+1)+2.$$

¿Qué hemos hecho? En lugar de a hemos escrito (a + 1). Los paréntesis son importantes; esta expresión sería incorrecta: 2a + 1 + 2. No sumamos uno a toda la expresión, sino que realmente convertimos a en una expresión una unidad mayor, es decir, (a + 1). Transformamos la expresión quitando el paréntesis.

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

Ahora una pequeña digresión sobre la divisibilidad. Si tenemos dos números, digamos p y q, que son divisibles entre un número, por ejemplo r, entonces también su suma es divisible entre r. Se cumple, por tanto:

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

Podemos sustituir, por ejemplo, los números p = 8, q = 20 y r = 4. Vemos que el cuatro divide tanto al ocho como al veinte. Y del mismo modo divide también a su suma 8 + 20 = 28.

¿Cómo lo aprovechamos en nuestro ejemplo? Separamos el lado derecho en los números p y q así:

$$p=2a+2;q=2$$

El número q, es decir, el dos, es trivialmente divisible entre dos. Y la expresión p también es divisible entre dos, porque nos lo dice la hipótesis. La expresión p corresponde exactamente a nuestra hipótesis, que suponemos verdadera. Y si p es divisible entre dos y a la vez q es divisible entre dos, entonces también su suma es divisible entre dos.

Una vez más sobre la hipótesis. Al principio hemos dicho que suponemos que se cumple

$$2\mid 2a+2.$$

Por eso, cuando durante la construcción de la demostración nos hemos encontrado con la expresión 2a + 2, hemos podido decir de ella que es divisible entre dos. Precisamente porque es nuestra hipótesis. Este suele ser el paso más difícil de la inducción matemática: entender cuándo y por qué se puede usar la hipótesis de inducción.

Con esto termina la inducción, la demostración se ha realizado con éxito y el enunciado se cumple.

Si quisieras, podrías descomponerlo de otra manera y no tendrías que usar la hipótesis. p = 2n y q = 2 + 2. El número q = 4 es trivialmente divisible entre dos y lo mismo p = 2n, porque al dividir entre dos nos queda el número n, que es natural, es decir, entero. De nuevo hemos obtenido dos expresiones que son ambas divisibles entre dos, así que también su suma es divisible entre dos.

En ambos casos, sin embargo, hemos demostrado que

1. la expresión dada se cumple para n = 1,
2. si la expresión se cumple para n, entonces se cumple también para n + 1.

De aquí ya podemos deducir:

• Sabemos que la expresión se cumple para n = 1.
• Si se cumple para n, tiene que cumplirse también para n + 1, es decir, también para 1 + 1, o sea, la expresión se cumple también para n = 2.
• Si se cumple para n, tiene que cumplirse también para n + 1, es decir, también para 2 + 1, o sea, la expresión se cumple también para n = 3.
• Si se cumple para n, tiene que cumplirse también para n + 1, es decir, también para 3 + 1, o sea, la expresión se cumple también para n = 4.
• Si se cumple para n, tiene que cumplirse también para n + 1, es decir, también para 4 + 1, o sea, la expresión se cumple también para n = 5.
• …

Segundo ejemplo

A continuación demostraremos por inducción matemática un enunciado sencillo:

$$2^n\ge 2n;n\in \mathbb{N}.$$

Primero el caso base: averiguamos si el enunciado se cumple para n = 1, el primer elemento de los números naturales de los que elegimos n.

$$\begin{array}{rcl}{2}^1& \ge & 2\cdot 1\\ 2& \ge & 2\end{array}$$

Esto se cumple trivialmente. Ahora pasamos al paso inductivo, en el que tenemos que averiguar si, cuando se cumple para n = a, se cumple también para n = a + 1. Nuestra hipótesis es, por tanto, que se cumple

$$2^a\ge 2a$$

y queremos demostrar:

$$2^{a+1}\ge 2(a+1)$$

El primer miembro lo desarrollamos primero con las reglas del cálculo con potencias y el segundo miembro simplemente lo desarrollamos quitando el paréntesis.

$$2\cdot 2^a\ge 2a+2$$

En el primer miembro usamos una suma en lugar de la multiplicación y el segundo lo dejamos sin cambios.

$$2^a+2^a\ge 2a+2$$

Ahora utilizamos la hipótesis. La hipótesis es un enunciado que suponemos que se cumple. En la inecuación tenemos en ambos miembros dos expresiones que se suman. Pero a la vez sabemos que

$$\begin{array}{rcl}{2}^a& \ge & 2a\\ 2^a& \ge & 2.\end{array}$$

La primera línea nos la dice la hipótesis y el segundo enunciado es trivial (el menor valor de 2^a se da para a = 1 y es justamente dos). Así que sabemos que en el primer miembro ambas expresiones son mayores o iguales que ambas expresiones del segundo miembro. Con ello hemos demostrado por inducción que, si la expresión se cumple para a, entonces se cumple también para (a + 1) y, como la expresión se cumple también para el uno, la expresión dada es verdadera.

Tercer ejemplo

Probemos a demostrar el siguiente enunciado:

$$3\mid n\Rightarrow 3\mid n^2;n\in \mathbb{N}$$

En palabras: si n es divisible entre tres, entonces también n² es divisible entre tres. Si n no es divisible entre tres, la expresión se cumple trivialmente (por la definición de implicación), así que nos ocuparemos de los casos en que n es divisible entre tres. Esto genera la sucesión de números naturales a_i=3, 6, 9, 12, 15… A partir de ahora nos moveremos en esta sucesión a_i.

Comenzamos la demostración por inducción con el caso base, es decir, comprobando si se cumple para el primer elemento. Recuerda que nos movemos en la sucesión a_i, así que tomamos el primer elemento de esta sucesión, es decir, el elemento a₁, que es el tres. Para el tres la expresión se cumple:

$$3\mid 3\Rightarrow 3\mid 3^2$$

Ahora pasamos al paso inductivo. Vemos que la sucesión a_i se podría escribir como 3n, donde n es un número natural. Es decir, el segundo elemento es tres unidades mayor que el anterior, etc. Supongamos ahora que la expresión se cumple para n y tenemos que asegurar que se cumpla también para (n + 3), que es la regla que genera el siguiente elemento de la sucesión en la que nos movemos. Escribimos primero la hipótesis:

$$3\mid n\Rightarrow 3\mid n^2$$

y después lo que queremos demostrar

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

Desarrollamos el paréntesis del lado derecho con la fórmula:

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

Ya casi hemos llegado. En el lado izquierdo tenemos una expresión que seguro es divisible entre tres, porque n es divisible entre tres por hipótesis (nos movemos solo en los números de la sucesión a_i) y el tres también es divisible entre tres. En el lado derecho tenemos primero n², que por hipótesis es divisible entre tres. En efecto, sabemos que n es divisible entre tres y la hipótesis dice que, si n es divisible entre tres, también n² es divisible entre tres:

$$3\mid n\Rightarrow 3\mid n^2$$

A continuación viene la expresión 6n, que es trivialmente divisible entre tres. Puedes imaginarlo como simplificar una fracción:

$$\frac{6n}{3}=2n$$

La variable n es un número natural, así que también el producto 2n será un número natural; es decir, al dividir entre tres hemos obtenido un número natural y la expresión 6n tiene que ser, por tanto, divisible entre tres. Y el nueve del final es de nuevo divisible entre tres. La expresión se cumple para el primer elemento y también en el paso inductivo, así que es verdadera.

Número de paréntesis en una expresión

El último ejemplo será algo atípico. Probaremos a demostrar el enunciado de que el número de paréntesis de una expresión simple es siempre par, para que veas que la inducción matemática se puede usar también en un contexto totalmente distinto de los números naturales. Al principio tenemos que definir qué es una expresión simple. Una expresión simple es:

• un número natural,
• si p es una expresión simple, entonces también (p²) es una expresión simple,
• si p y q son expresiones simples, entonces también (p + q) es una expresión simple.

Así que son expresiones simples: 12, 54, (5 + 6), (12 + 7), (6²), ((5 + 6)²). Y, por el contrario, estas no son expresiones simples:

• 1 + 2 → faltan los paréntesis exteriores,
• (1 + 2 → falta el paréntesis derecho,
• 13² → faltan los paréntesis exteriores,
• (1 + 2 + 3) → faltan paréntesis, la forma correcta de escribirla sería (1 + (2 + 3))

Una expresión simple puede surgir, por ejemplo, así. Al principio elegimos una expresión simple (a + b). Ahora sustituimos a por la expresión simple a = (c + d), con lo que obtenemos ((c + d) + b), y sustituimos b por un tres: ((c + d) + 3). Sustituimos c por un diez: ((10 + d) + 3) y por último sustituimos d por (5²): ((10 + (5²)) + 3). Es importante respetar los paréntesis; de lo contrario no funcionará.

Ahora demostraremos que una expresión simple contiene un número par de paréntesis (entre los números pares entra también el cero).

En el caso base de la inducción elegimos un primer elemento. En este caso, el primer elemento será la expresión simple más trivial, que es un número natural cualquiera. Así que tomamos

$$j=n;n\in \mathbb{N}.$$

Para la expresión j se cumple que el número de paréntesis es cero, así que el enunciado se cumple para el primer elemento. En el paso inductivo supondremos que tenemos dos expresiones simples p y q y que ambas tienen un número par de paréntesis. Entonces tenemos que demostrar que también las expresiones simples (p + q) y (p²) tienen un número par de paréntesis.

Primero la suma. Definimos además la función z(q), que devuelve el número de paréntesis de la expresión q. Entonces se cumple que la expresión (p + q) tiene z(p) + z(q) + 2 paréntesis. Es decir, tiene dos paréntesis más que la suma de los paréntesis de las expresiones p y q. Por hipótesis, tanto z(p) como z(q) son pares, así que, si sumamos tres números pares, obtenemos de nuevo un número par. Para este caso el enunciado se cumple.

Ahora la potencia. De nuevo se cumple la hipótesis de que la expresión simple p contiene un número par de paréntesis. La expresión (p²) contiene entonces z(p) + 2 paréntesis, es decir, de nuevo dos paréntesis más que la expresión p. También en este caso sumamos números pares, así que el resultado es par.

El enunciado se cumple para el primer elemento y se cumple también en el paso inductivo, por lo que el enunciado es verdadero.