Introducción
En esta entrada continuaremos con ejemplos de uso del principio de inducción en la resolución de problemas. Es una continuación de la entrada anterior. Como recordatorio, aquí está el principio de inducción en la forma en la que lo hemos estado usando:
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$.
Lo que nos interesa ahora es ver cómo el principio de inducción se mezcla con algunas de las heurísticas de resolución de problemas.
Inducción y trabajar hacia atrás
Lo que hemos hecho hasta ahora es lo siguiente. Tomamos un enunciado que depende de un entero $n$. Comenzamos probándolo para la base inductiva. Luego, suponemos la veracidad del enunciado para cierto entero $n$. A partir de ahí, intentamos conseguir la veracidad del enunciado para el entero $n+1$.
Como vimos cuando platicamos de trabajar hacia atrás, eso no siempre es lo más natural en la resolución de un problema. En algunas ocasiones nos conviene más empezar con el enunciado que queremos demostrar y mostrar que mediante pasos reversibles podemos llegar a algo cierto. Queremos aplicar esta idea para la demostración del paso inductivo.
Consideremos el siguiente ejemplo.
Problema. Demuestra que para todo entero no negativo $n$ se tiene que $$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$ es un número entero.
Solución. Tenemos que probar la afirmación para $n\geq 0$ entero. Procedemos por inducción sobre $n$. Si $n=0$, la expresión es igual a $0$, así que la afirmación es cierta. Supongamos entonces que
$$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$ es entero y consideremos la expresión
$$\frac{(n+1)^5}{5}+\frac{(n+1)^4}{2}+\frac{(n+1)^3}{3}-\frac{(n+1)}{30}.$$
Nuestro objetivo es mostrar que esta expresión es entera. Nos gustaría usar la hipótesis inductiva, así que queremos intentar encontrar dentro de esta expresión la expresión para $n$. Esto lo podemos hacer usando el binomio de Newton para abrir los binomios a potencias y luego agrupando. Tenemos que
\begin{align*}
\frac{(n+1)^5}{5}&=\frac{n^5+5n^4+10n^3+10n^2+5n+1}{5}\\
&=\frac{n^5}{5}+n^4+2n^3+2n^2+n+\frac{1}{5}\\
\frac{(n+1)^4}{2}&=\frac{n^4+4n^3+6n^2+4n+1}{2}\\
&=\frac{n^4}{4}+2n^3+3n^2+2n+\frac{1}{2}\\
\frac{(n+1)^3}{3}&=\frac{n^3+3n^2+3n+1}{3}\\&
=\frac{n^3}{3}+n^2+n+\frac{1}{3}\\
-\frac{n+1}{30}&=-\frac{n}{30}-\frac{1}{30}.
\end{align*}
Así, cuando hagamos la suma tenemos los términos
$$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30},$$ cuya suma es entera por hipótesis inductiva, $$n^4+2n^3+2n^2+n+2n^3+3n^2+2n+n^2+n,$$ que es entero pues $n$ es entero y $\frac{1}{5}+\frac{1}{2}+\frac{1}{3}-\frac{1}{30}=1$, de modo que la suma total es suma de enteros y por lo tanto es un entero. Esto termina la prueba por inducción.
$\square$
Si no comenzábamos a manipular la expresión para $n+1$, hubiera sido muy difícil, sólo a partir de la de $n$, llegar a la de $n+1$.
Inducción y generalización
Una forma sencilla de combinar inducción con generalización es la siguiente:
- Nos piden demostrar una afirmación para un natural muy específico.
- En vez de eso, construimos un problema más general que funcione «para todos los naturales».
- Resolvermos ese problema por inducción.
Veamos un ejemplo.
Problema. Muestra que $$\left(\frac{3+\sqrt{17}}{2}\right)^{2020}+
\left(\frac{3-\sqrt{17}}{2}\right)^{2020}$$ es un entero impar.
Solución. Sean $\alpha=\frac{3+\sqrt{17}}{2}$ y $\beta=\frac{3-\sqrt{17}}{2}$. Se pide mostrar que $\alpha^{2020}+\beta^{2020}$ es un entero impar. Mostraremos que, de hecho, $\alpha^n+\beta^n$ es un entero impar para todo entero $n\geq 1$. Vamos a proceder por inducción fuerte (hablaremos un poco más de eso más adelante).
El primer caso es $n=1$ y notemos que $\alpha^1+\beta^1=\alpha+\beta=3.$ Notemos también que $\alpha\beta=\frac{9-17}{4}=-2$, de modo que $\alpha^2+\beta^2=(\alpha+\beta)^2-2ab=9+4=13$, que también es impar. Supongamos ahora que sabemos que la afirmación es cierta para exponentes $n-1$ y $n$.
Consideremos el polinomio cuadrático $$(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=x^2-3x-2.$$ Como $\alpha$ y $\beta$ son raíces, tenemos que $\alpha^2-3\alpha-2=0$ y $\beta^2-3\beta -2=0$. Multiplicando estas igualdades por $\alpha^{n-1}$ y $\beta^{n-1}$ respectivamente, sumando ambas igualdades obtenidas, y despejando $\alpha^{n+1}+\beta^{n+1}$ llegamos a $$\alpha^{n+1}+\beta^{n+1}=3(\alpha^n+\beta^n)+2(\alpha^{n-1}+\beta^{n-1}).$$
De aquí la conclusión inductiva es inmediata. Como la hipótesis inductiva es que el resultado es cierto para los exponentes $n$ y $n-1$, entonces en el lado derecho tenemos una suma de un entero impar con un entero par, que es un entero impar. Esto muestra que la afirmación es cierta para cuando los exponentes son $n+1$.
Para demostrar el problema original, basta con hacer la observación de que, en particular, $\alpha^{2020}+\beta^{2020}$ es un entero impar.
$\square$
Hay otra forma de combinar inducción con generalización, pero es un poco más sofisticada. Para explicarla, es mejor comenzar con un ejemplo.
Problema. Demuestra que para todo entero $n\geq 1$ se tiene que $$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots + \frac{1}{n(n+1)} <1.$$
Antes de resolver el problema, intentemos hacer una solución «ingenua» que quiera usar inducción de manera directa. No hay ningún problema con hacer la base de inducción, pues para $n=1$ al lado izquierdo tenemos únicamente $\frac{1}{2}$ y al lado derecho $1$. Supongamos que el resultado es cierto para $n$, es decir, que $$\frac{1}{1\cdot 2}+\ldots + \frac{1}{n(n+1)} <1.$$
Llamémosle $M$ a la expresión del lado izquierdo. Lo que queremos probar ahora es que el resultado es cierto para $n+1$, es decir, que $M+\frac{1}{(n+1)(n+2)}<1$. Sabemos que $M<1$, pero ahora estamos sumando un término positivo adicional. Es posible que este término arruine la desigualdad, pues $M<1$ es una afirmación «muy débil». Veamos cómo darle la vuelta a esta dificultad.
Solución. Sea $P(n)$ la afirmación del problema. Consideremos la afirmación $Q(n)$ que dice que para todo entero $n\geq 1$ se tiene que
$$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots + \frac{1}{n(n+1)} =1-\frac{1}{n+1}.$$
Si logramos demostrar $Q(n)$, entonces $P(n)$ será cierta de manera inmediata, pues $1-\frac{1}{n+1}<1$. Vamos a demostrar $Q(n)$ por inducción.
Tenemos que $Q(1)$ es cierto pues en ambos lados de la igualdad queda $\frac{1}{2}$. Supongamos que $Q(n)$ es cierto. Usando esto, tenemos que
\begin{align*}
\frac{1}{1\cdot 2}+\ldots+\frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} &=\left(1-\frac{1}{n+1}\right)+\frac{1}{(n+1)(n+2)}\\
&=1-\frac{(n+2)-1}{(n+1)(n+2)}\\
&=1-\frac{1}{n+2},
\end{align*}
es decir, que $Q(n+1)$ es cierto. Así, por inducción $Q(n)$ es cierto para todo entero $n$ y con eso $P(n)$ también.
$\square$
Lo que sucedió fue lo siguiente. Al hacer el paso inductivo, intentamos mostrar que $P(n)$ implica $P(n+1)$. Pero esto es imposible pues $P(n)$ «es muy débil», o bien «pierde información de todo lo que está pasando». Sin embargo, cuando consideramos la afirmación auxiliar $Q(n)$, resulta que esta «tiene más información». Aquí, esta información es «qué tal lejos está la expresión de $1$ «
La afirmación $Q(n)$ tiene tanta información, que ahora sí con ella se puede probar $Q(n+1)$. Se termina el problema usando que $Q(n)$ implica $P(n)$. Así, la estrategia fue la siguiente:
- Se tiene una afirmación $P(n)$ que se quiere demostrar para todos los naturales. Hacer inducción no parece funcionar, pues $P(n)$ parece no ser suficiente para probar $P(n+1)$
- Se considera entonces una afirmación $Q(n)$ más fuerte (que implique a $P(n)$), pero para la cual $Q(n)$ sí pueda probar $Q(n+1)$.
- Se prueba $Q(n)$ por inducción, y se concluye que $P(n)$ es cierta.
Hay que ser cuidadosos. Parte del ingenio en usar esta estrategia consiste en poder identificar un balance en la generalización $Q(n)$ que necesitamos de modo que sí sirva para solucionar el problema original, pero que no sea demasiado ambiciosa como para que sea falsa.
Más ejemplos
Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas: