Introducción
En entradas anteriores ya hablamos acerca de la idea básica del principio de inducción y también vimos cómo la inducción puede interactuar con las heurísticas de trabajar hacia atrás y de generalización. En esta entrada hablaremos de dos formas adicionales y válidas en las que se puede hacer inducción.
Inducción fuerte
El principio de inducción funciona pues es un mecanismo que pasa por los números naturales «uno por uno». Al momento en el que suponemos la hipótesis inductiva para cierto natural $n$, lo que queremos hacer para continuar es mostrar la afirmación para el natural $n+1$. Es decir, el natural $n+1$ es el primer natural para el que todavía no sabemos que la afirmación funciona. Dicho de otra forma, para todo natural $m\leq n$ ya sabemos que la afirmación sí funciona.
Aunque típicamente usemos únicamente la afirmación para el paso $n$ para demostrar la validez del paso $n+1$, en realidad podríamos usar toda la información que ya tenemos de que la inducción se vale para todo $m$ entre la base inductiva y $n$. Esta es la idea detrás del principio de inducción fuerte.
Principio de inducción fuerte. 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(m)$ es cierto para todo $a\leq m \leq n$» implica la veracidad de la afirmación $P(n+1)$,
entonces la afirmación $P(n)$ es cierta para toda $n \geq a$.
Veamos un ejemplo de teoría de gráficas. No entraremos en detalles de las definiciones. Aunque no conozcas mucho de teoría de gráficas, es posible que de cualquier forma las definiciones te hagan sentido.
Problema. Un árbol es una gráfica que no tiene ciclos y que es conexa. Demuestra que todo árbol de $n$ vértices tiene $n-1$ aristas.
Solución. Lo vamos a demostrar por inducción sobre el número de vértices que tiene el árbol. Si el árbol tiene $1$ vértice, entonces el resultado es cierto, pues tiene $0$ aristas.
Tomemos ahora un entero $n$ y supongamos que el resultado es cierto para cuando el número de vértices es cualquier entero entre $1$ y $n$. Tomemos un árbol $T$ de $n+1$ vértices.
Tomemos una arista cualquiera de $T$ y quitémosla. Esto parte a $T$ en dos árboles (¡demuéstralo!) con, digamos $a$ y $b$ vértices, de modo que $a+b=n+1$.
Tenemos $1\leq a < n$ y $1\leq b <n$, así que cada uno de esos árboles tiene, por hipótesis inductiva, $a-1$ y $b-1$ aristas, respectivamente. Así, $T$ tiene esas aristas, y la que quitamos, es decir, $(a-1)+(b-1)+1=a+b-1=n$ aristas, como queríamos demostrar.
$\square$
Los que han estudiado teoría de gráficas quizás noten que pudimos haber evitado usar inducción fuerte si en vez de usar una arista arbitraria usábamos una que llegaba a un vértice hoja (de grado $1$). Haciendo eso se puede usar inducción «normal». La demostración anterior tiene la ventaja de no necesitar definir qué es una hoja.
Inducción de Cauchy
Hablemos ahora de otra variante. El principio de inducción es un mecanismo que nos permite probar una afirmación para los naturales «pasando por todos ellos» de una manera muy natural se prueba para el primero, luego para el siguiente, luego para el siguiente y así sucesivamente. Hay otras formas de cubrir a los números enteros.
Principio de inducción de Cauchy. Sea $P(n)$ una afirmación (o proposición o propiedad) que depende del número natural $n$. Si
- la afirmación $P(1)$ es cierta,
- la veracidad de la afirmación $P(n)$ implica la veracidad de la afirmación $P(2n)$ y
- la veracidad de la afirmación $P(n)$ para un $n>a$ implica la veracidad de la afirmación $P(n-1)$,
entonces la afirmación $P(n)$ es cierta para toda $n \geq 1$.
Intuitivamente, lo que está pasando es que al probar $P(1)$ y la segunda afirmación, estamos probando $P(2)$, de ahí $P(4)$, de ahí $P(8)$ y en general $P(n)$ para cuando $n$ es potencia de $2$. Luego, con $P(4)$ y la tercera afirmación sale $P(3)$. Con $P(8)$ y la tercera afirmación sale $P(7), P(6),P(5)$. Esto garantiza cubrir todos los naturales pues para cualquier natural $n$ hay una potencia de dos $2^m$ mayor que él para la que sabemos que el resultado es cierto, y de ahí con la tercera afirmación «vamos bajando cubriendo todos los naturales», incluido $n$.
Como ejemplo, presentamos una demostración de la desigualdad entre la media aritmética y la media geométrica,
Problema. Sea $n$ un entero positivo y $x_1,x_2,\ldots,x_n$ números reales positivos. Demuestra que $$\frac{x_1+x_2+\ldots+x_n}{n}\geq \sqrt[n]{x_1x_2\cdots x_n}.$$
Solución. Vamos a proceder por inducción de Cauchy sobre $n$. Sea $P(n)$ la afirmación del problema.
En el caso $n=1$ tenemos sólo un real $x_1$ y tenemos que demostrar que $\frac{x_1}{1}\geq \sqrt[1]{x_1}$, lo cual es cierto pues en ambos lados tenemos $x_1$. Así, $P(1)$ es cierta.
Para el resto de la demostración, será útil que probemos también por separado el caso para dos números, es decir, $P(2)$. Pero esto es sencillo pues si tenemos reales positivos $a$ y $b$, entonces $\frac{a+b}{2}\geq \sqrt{ab}$ es equivalente a $a-2\sqrt{ab}+b\geq 0$, la cual es cierta pues el lado izquierdo es el número no negativo $(\sqrt{a}-\sqrt{b})^2$.
Ahora veremos que $P(n)$ implica $P(2n)$. Supongamos la veracidad de $P(n)$ y tomemos $2n$ números reales $x_1,x_2,\ldots,x_{2n}$. Queremos demostrar que $$\frac{x_1+\ldots+x_{2n}}{2n}\geq \sqrt[2n]{x_1\cdots x_{2n}}.$$ Llamemos $A$ al lado izquierdo y $G$ al lado derecho.
Sea $B$ la media aritmética de $x_1,\ldots, x_n$ y $C$ la de $x_{n+1},\ldots, x_{2n}$. Aplicando por separado $P(n)$ a estos números, tenemos que
\begin{align*}
B:=\frac{x_1+\ldots+x_n}{n}&\geq \sqrt[n]{x_1\cdots x_n}\\
C:=\frac{x_{n+1}+\ldots+x_{2n}}{n}&\geq \sqrt[n]{x_{n+1}\cdots x_{2n}}\\
\end{align*}
Notemos que $A=\frac{B+C}{2}$. Aplicando $P(2)$ a los números $B$ y $C$ tenemos que
\begin{align*}
A&=\frac{B+C}{2}\\
&\geq \sqrt[2]{BC} \\
&\geq \sqrt[2]{\sqrt[n]{x_1\cdots x_n} \cdot \sqrt[n]{x_{n+1}\cdots x_{2n}}}\\
& = G.
\end{align*}
Es decir, $P(2n)$ es cierta.
Para terminar con la inducción de Cauchy, el último paso es suponer la veracidad de $P(n)$ para $n>1$ y con ella demostrar la veracidad de $P(n-1)$. Supongamos entonces la veracidad de $P(n)$ y tomemos $n-1$ números $x_1,\ldots, x_{n-1}$. Queremos usar la veracidad de $P(n)$, así que tenemos que «inventarnos» otro número $m$ para poder aplicar $P(n)$. Tomemos $m=\frac{x_1+\ldots+x_{n-1}}{n-1}$, es decir, la media aritmética de los números de $x_1$ hasta $x_{n-1}$.
Observemos que $$\frac{x_1+\ldots+x_{n-1}+m}{n}=m.$$ Usando la veracidad de $P(n)$ para los números $x_1,\ldots, x_{n-1},m$ tenemos que $$m=\frac{x_1+\ldots+x_{n-1}+m}{n}\geq \sqrt[n]{x_1\cdots x_{n-1}m}.$$
Dividiendo entre $\sqrt[n]{m}=m^{1/n}$ en ambos extremos de la cadena, obtenemos $$m^{\frac{n-1}{n}}\geq \sqrt[n]{x_1 \cdots x_{n-1}}.$$
Elevando ambos lados de esta desigualdad a la $n/(n-1)$ obtenemos
$$m\geq \sqrt[n-1]{x_1 \cdots x_{n-1}}.$$
Esto es exactamente lo que queríamos probar. Con esto se comprueba la veracidad de $P(n-1)$ y así terminamos la inducción de Cauchy.
$\square$
La elección de $m$ en la última parte de la demostración parece un poco sacada de la manga. En realidad, sí tiene una cierta motivación. En la hipótesis $P(n)$ tenemos a la izquierda $\frac{x_1+x_2+\ldots+x_n}{n}$, pero lo que queremos es tener $\frac{x_1+x_2+\ldots+x_{n-1}}{n-1}$. Nuestra elección de $x_n=m$ vino de igualar ambas expresiones y despejar $x_n$.
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: