Introducción
El principio de inducción es una de las piedras angulares de las matemáticas y de la resolución de problemas. Es altamente probable que ya lo hayas utilizado previamente, en cursos como Álgebra Superior I y II, en Álgebra Lineal, en Cálculo y varios otros.
En esta entrada y las siguientes repasaremos la idea general del principio de inducción, pero además veremos lo flexible que puede ser en la resolución de problemas.
La idea general que debes tener cuando hagas inducción es pensar en Tlaloc (dios de la lluvia). Imagina que Tlaloc decide que llueva hoy, y además decide que si llueve un día, entonces lloverá también al día siguiente. Como llueve hoy, entonces lloverá mañana, pero como llueve mañana entonces lloverá pasado mañana. De hecho, ¡va a llover todos los días a partir de hoy!
De manera general, el principio de inducción sirve para cuando se quieren probar afirmaciones «para todo número natural $n$» y en donde para probar la afirmación para un valor $n$ es útil tener la validez de la afirmación para los valores anteriores. Sin embargo, se puede también utilizar para probar afirmaciones «a partir de cierto natural». Enunciamos esta versión a continuación.
Principio de inducción. Sea $P(n)$ una afirmación (o proposición o propiedad) que depende del número natural $n$. Si
- la afirmación $P(a)$ es cierta y
- la veracidad de la afirmación $P(n)$ implica la veracidad de la afirmación $P(n+1)$,
entonces la afirmación $P(n)$ es cierta para toda $n \geq a$.
En estos términos, a probar la afirmación para $a$ se le conoce como probar la base de inducción. Suponer la veracidad de $P(n)$ para una $n$ se conoce como suponer la hipótesis inductiva, y a probar la veracidad de $P(n+1)$ se le conoce como hacer el paso inductivo. Así, para hacer una prueba por inducción se tienen que hacer los siguientes pasos:
- Probar la base de inducción, osea, mostrar que $P(a)$ es válido.
- Suponer, libremente, la hipótesis inductiva, es decir, suponer que $P(n)$ cierto.
- A partir de la hipótesis inductiva, y el resto de las hipótesis del problema, hacer el paso inductivo, es decir, demostrar $P(n+1)$.
Es muy importante hacer estos tres pasos. Si no se prueba la base de inducción, es como si Tlaloc no decidiera que lloviera hoy: no hay forma de saber qué pasara. Si no se hace el paso inductivo, es como si Tlaloc no dijera nada de la lluvia de un día a partir del anterior.
La creatividad en el uso de la inducción en la resolución de problemas reside en varios aspectos. A veces:
- Se requiere ingenio para probar el caso base.
- Se requiere ingenio para saber exactamente cómo usar la hipótesis inductiva para hacer el paso inductivo.
- Se requiere crear una afirmación auxiliar $Q(n)$ más fuerte que implique a $P(n)$, tal qué $Q(n)$ sí se pueda probar por inducción, pero $P(n)$ no, de lo cual veremos ejemplos en siguientes entradas.
Problemas con solución
Veamos algunos ejemplos de problemas que se pueden resolver utilizando induccicón. En el primer problema vamos a ser muy explícitos en cómo estamos ejecutando la inducción. Esto te puede ayudar cuando estas haciendo tus primeras pruebas de inducción: te ayudará a ser explícito en demostrar la base, en suponer la hipótesis inductiva y en hacer el paso inductivo.
En algunas otras de las demostraciones, vamos a ser un poco más flexibles con cómo se escribe la demostración. No hay que ser totalmente explícitos en qué parte de demostración por inducción se está haciendo. Esto te puede ayudar para cuando ya estas escribiendo una prueba más larga y la parte inductiva sólo es un pequeño fragmento del argumento.
Problema. Sea $n\geq 1$ un número entero y $a_n>a_{n-1}>\ldots>a_1>0$ números reales. Considera todas las expresiones que puedes hacer de la forma $$e_1a_1+e_2a_2+\ldots+e_na_n$$ donde cada $e_i$ es $1$ o $0$. Demuestra que al pasar por todas las $2^n$ posibilidades para las $e_i$ se forman por lo menos $\binom{n+1}{2}$ números diferentes.
Solución. Vamos a proceder por inducción sobre $n$. Hagamos primero la base de inducción. Como queremos demostrar la afirmación para toda $n\geq 1$, el caso base es $n=1$. Cuando $n=1$, tenemos un sólo número real $a_1>0$ y lo que tenemos que demostrar es que hay al menos $\binom{2}{2}=1$ valor en las expresiones que se pueden formar. Si $e_1=0$ o $1$, obtenemos las expresiones $0$ y $a_1$ respectivamente, que son al menos dos. Esto prueba el caso base.
Ahora supongamos la hipótesis inductiva. Es decir, suponemos libremente que para cierta $n$, cada que tomamos $n$ números reales se cumple la afirmación del problema, es decir, que al pasar por las $2^n$ posibilidades de $e_i$, se obtienen al menos $\binom{n+1}{2}$ expresiones diferentes.
La parte final es hacer el paso inductivo. Es decir, a partir de todas las hipótesis del problema, de la hipótesis inductiva, y de otras ideas, tenemos que probar la afirmación para $n+1$. Así, tomemos $n+1$ números reales $$a_{n+1}>a_n>\ldots>a_1>0.$$ Tenemos que mostrar que usando coeficientes $0$ y $1$ podemos formar al menos $\binom{n+2}{2}$ números distintos.
Una buena idea es aprovechar que ya sabemos que los números
$$a_n>\ldots>a_1>0$$ ya hacen varias expresiones. Podemos aplicar la hipótesis inductiva a estos números, y con ello logramos conseguir al menos $\binom{n+1}{2}$ expresiones diferentes. Notemos que estas expresiones también sirven para cuando tenemos a $a_{n+1}$ y le ponemos coeficiente $e_{n+1}=0$. Lo que tenemos que hacer ahora es conseguir $\binom{n+2}{2}-\binom{n+1}{2}=n+1$ expresiones nuevas.
Consideremos la expresión $S=a_1+a_2+\ldots+a_n$ en la que todos los coeficientes son $1$. Esta es claramente mayor que cualquiera de las otras que ya tenemos. Además, todas las expresiones $S+a_{n+1}$, $S+a_{n+1}-a_1$, $S+a_{n+1}-a_2$, $\ldots$, $S+a_{n+1}-a_n$ son mayores que $S$ (pues $a_{n+1}$ es el más grande de los $a_i$’s), son todas diferentes, y son de la forma deseada (pues cada $a_i$ con $1\leq i \leq n$ está en $S$).
De esta forma, conseguimos $n+1$ expresiones distintas y todas ellas mayores que $S$, así que distintas de todas las dadas por la hipótesis inductiva. Con esto completamos la demostración.
$\square$
La inducción sirve para probar afirmaciones que dependen de un número natural. Sin embargo, no siempre es inmediato de dónde sale este natural. A veces ese natural aparece simplemente como el tamaño de algún conjunto involucrado. A veces hay que hacer una demostración para «todos los polinomios» y entonces podríamos intentar hacer inducción sobre el grado del polinomio. En otro problema puede que se tenga que mostrar algo «para todas las matrices» y entonces tal vez tengamos que demostrarlo por inducción sobre las dimensiones de la matriz.
Problema. Se dibuja una cantidad finita de lineas en el espacio de modo que no haya tres de ellas que pasan por un mismo punto. Estas líneas definen regiones en el plano. Muestra que se pueden colorear estas regiones de blanco o negro de modo que no haya dos regiones del mismo color que tengan un lado en común.
El problema no tiene ningún número natural explícitamente en el enunciado. Sin embargo, se pide demostrar algo para una cantidad finita de cosas, así que basta probar la afirmación para $n$ cosas, para todo entero $n\geq 0$. De esta forma, la variable «cantidad de líneas que tenemos» ya es una variable sobre la cual podemos hacer inducción. Hagamos la demostración así.
Solución. Procedamos por inducción sobre el número de líneas. Si tenemos $0$ líneas, sólo hay una región en el plano. La pintamos de blanco.
Ahora, supongamos que cada que tenemos $n$ líneas, no tres de ellas por un punto, podemos hacer una coloración de su conjunto de regiones $R$ de modo que no haya dos adyacentes del mismo color.
Tomemos cualquier conjunto de $n+1$ líneas. Tomemos una de ellas $L$ e ignorémosla por el momento. Por hipótesis inductiva, podemos hacer una coloración para las $n$ líneas que quedan. Al regresar $L$ se hacen nuevas regiones. A las regiones que quedan de un lado de $L$, las dejamos del color que ya tenían. A las que están del otro lado de $L$, les intercambiamos el color (blanco a negro y viceversa).
El nuevo acomodo funciona pues todas las regiones de $R$ totalmente contenidas en alguno de los lados de $L$ siguen sin problemas. Y aquellas regiones de $R$ cortadas por $L$ sólo pueden tener problemas con un lado que caiga sobre $L$. Pero de estos problemas tampoco hay pues de un lado quedaron de un color, y del otro del otro.
$\square$
Observa que en el problema anterior ya no estamos haciendo los pasos de la inducción tan «explícitos».
A veces hay problemas en los que hay una variable entera, pero no necesariamente hay que aplicar inducción para esa variable, sino para otro parámetro que introduzcamos.
Problema. Dado un entero positivo $n$ y un real $x\geq 0$, muestra que $$\floor{x}+\floor{x+\frac{1}{n}}+\floor{x+\frac{2}{n}}+\cdots+\floor{x+\frac{n-1}{n}}=\floor{nx}.$$
Recuerda que $\floor{y}$ es el mayor entero que sea menor o igual a $y$.
Solución. El problema con hacer inducción en $n$ es que no hay una forma sencilla de relacionar el resultado para $n$ y el resultado para $n+1$. Tampoco podemos hacer «inducción sobre $x$» porque $x$ es un número real.
El truco para el problema es probar el resultado para todas las $x$ en el intervalo $[\frac{k}{n},\frac{k+1}{n})$ para todo entero $k\geq 0$. Con esos intervalos cubrimos a todos los reales positivos, y por lo tanto cubrimos todas las posibilidades para $x$. Para probar que se vale en esos intervalos, vamos a proceder por inducción sobre $k$.
Si $k=0$, entonces queremos mostrar el resultado para el intervalo $[0,\frac{1}{n})$. Para las $x$ en este intervalo, cada uno de los términos $x+\frac{i}{n}$ (para $i-0,1,\ldots,n-1$) es menor que $1$ y por lo tanto el lado izquierdo de la igualdad que queremos mostrar tiene puros sumandos $0$ y entonces es igual a $0$. También para las $x$ en este intervalo tenemos $nx<1$, y así el lado derecho también es $0$. Esto prueba la base inductiva.
Supongamos ahora que el resultado es cierto para $x$ en el intervalo $[\frac{k-1}{n},\frac{k}{n})$ para cierto entero $k$. Esto quiere decir que
$$\floor{x}+\floor{x+\frac{1}{n}}+\floor{x+\frac{2}{n}}+\cdots+\floor{x+\frac{n-1}{n}}=\floor{nx}.$$
Tomemos ahora un entero $y$ en el intervalo $[\frac{k}{n},\frac{k+1}{n})$. Notemos que $x=y-\frac{1}{n}$ está en el intervalo anterior, de modo que cumple la igualdad de la hipótesis inductiva. Notemos además que si en
$$\floor{y}+\floor{y+\frac{1}{n}}+\floor{y+\frac{2}{n}}+\cdots+\floor{y+\frac{n-1}{n}}$$
substituimos $y=x+\frac{1}{n}$, obtenemos
$$\floor{x+\frac{1}{n}}+\floor{x+\frac{2}{n}}+\floor{x+\frac{3}{n}}+\cdots+\floor{x+\frac{n}{n}}.$$
El último sumando es $\floor{x+1}=\floor{x}+1$, de modo que en el lado izquierdo tenemos todos los sumandos del lado izquierdo de la hipótesis inductiva y un $1$. Así, el lado izquierdo es igual a $$\floor{nx}+1=\floor{nx+1}=\floor{ny},$$ como queríamos mostrar.
$\square$
Más ejemplos
Puedes encontrar más ejemplos en la Sección 2.1 del Problem Solving through Problems de Loren Larson. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. Así mismo, aquí en el blog hay otras entradas en las que se hacen pruebas por inducción.
