Archivo del Autor: Leonardo Ignacio Martínez Sandoval

Leonardo Ignacio Martínez Sandoval

Acerca de Leonardo Ignacio Martínez Sandoval

Hola. Soy Leonardo Martínez. Soy Profesor de Tiempo Completo en la Facultad de Ciencias de la UNAM. Hice un doctorado en Matemáticas en la UNAM, un postdoc en Israel y uno en Francia. Además, me gusta colaborar con proyectos de difusión de las matemáticas como la Olimpiada Mexicana de Matemáticas.

Seminario de Resolución de Problemas: Variantes del principio de inducción

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

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.

Árbol con $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$.

Después de quitar la arista

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:

Seminario de Resolución de Problemas: Principio de inducción combinado con heurísticas

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

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:

Álgebra Superior II: Teoremas de Fermat y de Wilson

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En las entradas anteriores hablamos de congruencias, del anillo de enteros módulo $n$ y vimos algunos problemas. La gran ventaja de trabajar en $\mathbb{Z}_n$, o bien, de trabajar módulo $n$, es que para $n$ pequeña hay una cantidad pequeña de elementos y entonces las operaciones se vuelven muy sencillas.

Problema. Determina cuál es el residuo obtenido de dividir $705\cdot 702+714\cdot 711$ al dividirse entre $7$.

Solución. Tenemos que $705$, $702$, $714$ y $711$ los podemos poner como un múltiplo de $7$ más un residuo como sigue: $700+5$, $700+2$ y $714=714+0$, $711=707+4$. Así, $705\equiv 5\pmod 7$, $702\equiv 2 \pmod 7$, $714\equiv 0 \pmod 7$ y $711\equiv 4 \pmod 7$. Así, trabajando módulo $7$ tenemos que:

\begin{align*}
705\cdot 702+714\cdot 711 \equiv 5\cdot 2 + 0\cdot 4 \equiv 10 + 0 \equiv 10 \equiv 3 \pmod 7
\end{align*}
De esta forma, $705\cdot 702+714\cdot 711$ deja residuo $3$ al dividirse entre $7$.

$\square$

Trabajando de esta forma, podemos encontrar el residuo al dividirse por $n$ de expresiones que involucran sumas y productos. El objetivo de esta entrada es entender qué sucede cuando queremos encontrar el residuo de expresiones que tienen potencias y factoriales.

Pequeño teorema de Fermat

Intentemos entender qué sucede con las potencias de un número $a$ en cierto módulo $n$.

Ejemplo. Imagina que tomamos al número $3$ y queremos elevarlo a distintas potencias y entender el residuo que deja al dividirse entre $7$. Tenemos, trabajando módulo $7$:
\begin{align*}
3^0\equiv 1\\
3^1\equiv 3\\
3^2\equiv 9 \equiv 2\\
3^3=27\equiv 21+6\equiv 6
\end{align*}

Nota que podríamos seguir, poniendo $3^4=81$. Pero podemos ahorrarnos trabajo pues $3^4\equiv 3\cdot 3^3 \equiv 3 \cdot 6 \equiv 18\equiv 4$, en donde usamos que ya sabíamos que $3^3\equiv 6$. Del mismo modo, podemos seguir substituyendo cada potencia en la siguiente para obtener
\begin{align*}
3^5\equiv 3\cdot 4\equiv 12\equiv 5\\
3^6\equiv 3\cdot 5 = 15\equiv 1\\
3^7\equiv 3\cdot 1 = 3\\
3^8\equiv 3\cdot 3 = 9 \equiv 2
\end{align*}

Podríamos seguir y seguir, pero ya no tiene mucho caso. A partir de aquí es fácil convencerse de que los residuos se ciclan: $1,3,2,6,4,5,1,3,2,6,4,5,1\ldots$. Notemos que si la potencia es múltiplo de $6$, entonces el residuo será $1$, es decir, $3^{6k}\equiv 1 \pmod 7$. Esto es fantástico, pues entonces si queremos determinar el residuo de dividir, digamos, $3^{605}$ entre $7$, basta ver que módulo $7$ tenemos $$3^{605}=3^{600}\cdot 3^5 \equiv 1\cdot 5 \equiv 5,$$

en donde estamos usando lo que mencionamos para $k=100$ y que ya hicimos $3^5$ módulo $7$.

A partir del ejemplo anterior, nos damos cuenta de que es importante saber cuándo $a^m\equiv 1\pmod n$, pues en ese momento las potencias «se empiezan a ciclar». El pequeño teorema de Fermat es un resultado que podemos aplicar cuando trabajamos módulo un número primo $p$. Dice que la potencia $p-1$ funciona para esto.

Teorema. Si $p$ es un número primo y $p$ no divide a $a$, entonces $p$ divide a $a^{p-1}-1$ o, dicho en otras palabras $a^{p-1}\equiv 1 \pmod p$.

Demostración. Afirmamos que los números $a$, $2a$, $3a$, $\ldots$, $(p-1)a$ dejan todos ellos residuos distintos al dividirse entre $p$ y, además, que ninguno de esos residuos es $0$. Probemos esto. Tomemos $0<i<j<p-1$. En una entrada anterior vimos que $[a]_p$ tiene inverso en $Z_p$. Sea $[b]_p$ su inverso. Si $[ia]_p=[ja]_p$, entonces multiplicando por $[b]_p$ de ambos lados tendríamos $$[i]_p=[i(ab)]_p=[j(ab)]_p=[j]_p.$$

Pero como $i$ y $j$ están entre $1$ y $p-1$, esto implica que $i=j$. Ninguno es cero pues si $[ia]_p=[0]_p$, entonces al multiplicar por $b$ tendríamos la contradicción $[i]_p=[i(ab)]_p=[0b]_p=[0]_p$. Esto muestra la afirmación.

Así, usando la afirmación en el segundo paso de la siguiente cadena módulo $p$, tenemos:
\begin{align*}
(p-1)! a^{p-1} &= (a)(2a)(3a)\cdots((p-1)a)\\
&\equiv 1\cdot 2 \cdot \ldots \cdot (p-1)\\
&= (p-1)!.
\end{align*}

El número $(p-1)!$ no es divisible entre $p$, pues es producto de puros números menores que $p$, de modo que $\text{MCD}(p, (p-1)!)=1$, así que tiene inverso módulo $p$, de modo que podemos cancelarlo de la congruencia anterior multiplicando en ambos lados por su inverso. De aquí obtenemos la igualdad que queremos: $$a^{p-1}\equiv 1 \pmod p.$$

$\square$

Ya que demostramos este teorema, podemos aprovecharlo para resolver problemas que parecen ser difíciles.

Problema. Demuestra que $13$ divide a $25^{181}-181^{25}$

Solución. Notemos primero que $13$ es primo y que no divide ni a $25$ ni a $181$. Por el pequeño teorema de Fermat, tenemos módulo $13$ que $25^{12}\equiv 1$ y que $181^{12}\equiv 1$. Así, módulo $13$ tenemos que $$25^{181}\equiv 25^{15\cdot 12}\cdot 25 \equiv 25 \equiv 12,$$ y que $$181^{25}\equiv 181^{2\cdot 12}\cdot 181\equiv 181 \equiv 12.$$

De esta forma, $25^{181}-181^{25}\equiv 12-12\equiv 0\pmod {13}$, es decir, $13$ divide a $25^{181}-181^{25}$

$\triangle$

Teorema de Wilson

En la demostración del teorema de Fermat aparece la expresión $(p-1)!$. ¿Qué residuo dejará al dividirse entre $p$? Hagamos una prueba.

Problema. Encuentra el residuo que se obtiene al dividir $10!$ entre $11$.

Solución. Para no trabajar con números tan grandes, notemos que en $$10!=1\cdot 2\cdot 3\cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10$$ podemos cambiar a $6,7,8,9,10$ por $-5, -4, -3, -2, -1$ al trabajar módulo $11$, así que basta encontrar $-(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2$ módulo $11$. Notemos que $3\cdot 4\equiv 12 \equiv 1 \pmod {11}$ y que $2\cdot 5 =10 \equiv -1 \pmod {11}$. Así, $$10!\equiv -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 \equiv -(1\cdot 1 \cdot -1)^2 \equiv -1 \equiv 10 \pmod {11},$$

es decir, el residuo que deja $10!$ al dividirse entre $11$ es $10$.

$\triangle$

El teorema de Wilson ayuda a cuando queremos encontrar el residuo de un factorial al dividirse entre un número primo. Una de las ideas del ejercicio anterior fue buena: nos conviene agrupar a números del factorial en productos sencillos. Lo más conveniente es que agrupemos a cada número con su inverso multiplicativo, pues así obtendremos un $1$. Eso lo podemos hacer si el inverso es diferente. La siguiente proposición nos ayuda a entender cuándo pasa esto.

Proposición. Sea $p$ un número primo. Los únicos elementos en $\mathbb{Z}_p$ que son inversos de sí mismos son $[1]_p$ y $[p-1]_p$.

Demostración. Claramente $[1]_p$ y $[p-1]_p=[-1]_p$ son inversos multiplicativos de sí mismos, pues $1\cdot 1=1=(-1)\cdot(-1)$. Ahora, si tenemos $a$ tal que $a$ es inverso multiplicativo de sí mismo, tenemos que $[a^2]_p\equiv [1]_p$, que por definición quiere decir que $p$ divide a $a^2-1=(a+1)(a-1)$. Cuando un primo divide a un producto, tiene que dividir a uno de los factores. Entonces $p$ divide a $a+1$ o a $a-1$, y obtenemos, respectivamente, que $[a]_p=[-1]_p=[p-1]_p$ o que $[a]_p=[1]_p$, como queríamos.

$\square$

Estamos listos para enunciar y demostrar el teorema de Wilson.

Teorema. Si $p$ es un número primo, entonces $p$ divide a $(p-1)!+1$ o, dicho en otras palabras, $(p-1)!\equiv -1 \pmod p$.

Demostración. Si $p=2$, el resultado es inmediato. Supongamos que $p\geq 3$. En $(p-1)!$ aparecen todos los números de $1$ a $p-1$. Todos ellos son primos relativos con $p$, así que tienen inverso módulo $p$. Ese inverso también aparece en $(p-1)!$. Así, podemos agrupar esos números en $(p-3)/2$ parejas de inversos multiplicativos, en donde por la proposición anterior sólo nos va a sobrar el $1$ y el $-1$. De esta forma, $$(p-1)!\equiv (1)(-1)(1\cdot 1\cdot \ldots\cdot 1) \equiv -1 \pmod p,$$

en donde en la expresión intermedia tenemos un $1$, un $-1$ y $(p-3)/2$ unos, uno por cada pareja de inversos que se multiplicaron. Esto termina la prueba.

$\square$

Veamos una posible aplicación.

Problema. Determina el residuo que se obtiene al dividir $15!+16!+17!$ entre $17$.

Solución. Notemos que $17$ divide a $17!$, así que $17!\equiv 0 \pmod {17}$. Por el teorema de Wilson, $16!\equiv -1 \pmod {17}$. Podemos multiplicar esa igualdad por $-1$ para obtener módulo $17$ que $$15! = 15! (-1)(-1) \equiv 15! \cdot 16 \cdot (-1) \equiv 16! (-1)\equiv (-1)(-1)\equiv 1.$$ Así, $15!+16!+17!\equiv 1 + (-1) + 0 \equiv 0 \pmod {17}$.

$\square$

Una solución alternativa es darse cuenta de que $$15!+16!+17!=15!(1+16)+17\cdot 16!=17\cdot (15!+16!)$$ y por lo tanto es múltiplo de $17$. Aunque tengamos herramientas fuertes, ¡siempre hay que recordar los básicos!

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Lineal I: Transformaciones lineales en bases, conjuntos independientes y generadores

Por Leonardo Ignacio Martínez Sandoval

11 respuestas

Introducción

El objetivo de esta entrada es entender qué efecto tienen las transformaciones lineales en bases, en conjuntos linealmente independientes y en conjuntos generadores. En la siguiente lista recordamos brevemente estas nociones:

  • Una transformación lineal $T:V\to W$ entre espacios vectoriales $V$ y $W$ es una función que «abre sumas» (es decir $T(x+y)=T(x)+T(y)$) y «saca escalares» (es decir $T(cx)=cT(x)$). Recuerda que es necesario que $V$ y $W$ estén sobre el mismo campo, cosa que asumiremos cuando hablemos de transformaciones lineales.
  • Un conjunto de vectores $\{v_1,\ldots, v_n\}$ en $V$ es linealmente independiente si la única combinación lineal de ellos que da $0$ es la trivial, osea en la que todos los coeficientes son $0$.
  • Si cualquier vector de un espacio vectorial $V$ puede escribirse como combinación lineal de un conjunto de vectores $S=\{v_1,\ldots,v_n\}$, entonces decimos que $S$ genera a $V$.
  • Un conjunto de vectores en $V$ es base si es linealmente independiente y genera a $V$.

La idea de esta entrada es entender lo siguiente:

  • ¿Cuándo las imágenes de linealmente independientes/generadores/bases son linealmente independientes/generadores/bases tras aplicar una transformación lineal?
  • ¿Cómo saber si una transformación lineal es inyectiva?
  • ¿Cómo el efecto de transformaciones lineales en bases nos permite determinar exactamente qué le hacen al resto de los vectores?

Exploración

Tomemos espacios vectoriales $V$, $W$ y una transformación lineal $T:V\to W$. Si comenzamos con un conjunto $S=\{v_1,\ldots,v_n\}$ de vectores en $V$ que es linealmente independiente (o generador, o base) en $V$, ¿cuándo sucede que $T(S)=\{T(v_1),\ldots,T(v_n)\}$ es linealmente independiente (o generador, o base, respectivamente) en $W$?

Esto definitivamente no sucede siempre. La tranformación $Z:\mathbb{R}^3\to \mathbb{R}[x]$ que manda a todo vector $(x,y,z)$ al polinomio $0$ es una transformación lineal. Sin embargo, a la base canónica $\{e_1,e_2,e_3\}$ la manda al conjunto $\{0,0,0\}=\{0\}$, que no es un conjunto ni linealmente independiente, ni generador de los polinomios con coeficientes reales.

De esta forma, tenemos que pedirle más a la transformación $T$ para que preserve las propiedades mencionadas.

Intuitivamente, si la imagen de $T$ no cubre a todo $W$, entonces los vectores de la forma $T(v)$ con $v$ en $V$ no deberían de poder generar a $W$. Así, para que $T$ mande generadores a generadores, tiene que pasar que «$T$ pase por todo $W$». Esta noción queda capturada formalmente al pedir que $T$ sea suprayectiva.

Del mismo modo, también intuitivamente si «$T$ manda elementos distintos al mismo elemento», entonces perderemos familias linealmente independientes al aplicarla. Así, para preservar conjuntos linealmente independientes, necesitamos que vectores distintos vayan a valores distintos. En términos formales, necesitamos que $T$ sea inyectiva.

Resultados principales de transformaciones lineales en bases, generadores y linealmente independientes

El primer resultado es que los requisitos que descubrimos intuitivamente en la sección pasada son suficientes.

Teorema. Sea $T:V\to W$ una transformación lineal y $S=\{v_1,\ldots,v_n\}$ un conjunto de vectores de $V$. Entonces:

  • Si $T$ es inyectiva y $S$ es linealmente independiente, entonces $T(S)$ es linealmente independiente.
  • Cuando $T$ es suprayectiva y $S$ es generador, entonces $T(S)$ es generador.
  • Si $T$ es biyectiva y $S$ es base, entonces $T(S)$ es base.

Demostración. Comencemos suponiendo que $T$ es inyectiva y $S$ es linealmente independiente. Entonces $T(v_1),\ldots,T(v_n)$ son todos distintos. Tomemos una combinación lineal de elementos de $T(S)$ igual a cero, es decir, $$a_1T(v_1)+a_2T(v_2)+\ldots+a_nT(v_n)=0.$$ Debemos mostrar que todos los coeficientes son iguales a cero. Como $T$ es transformación lineal, podemos juntar las sumas y productos escalares como sigue: $$T(a_1v_1+a_2v_2+\ldots+a_nv_n)=0=T(0).$$

Como $T$ es inyectiva, esto implica que $$a_1v_1+a_2v_2+\ldots+a_nv_n=0,$$ pero como $S$ es linealmente independiente, concluimos que $$a_1=\ldots=a_n=0.$$ Así, $T(S)$ es linealmente independiente.

Supongamos ahora que $T$ es suprayectiva y $S$ es generador. Tomemos un $w\in W$. Como $T$ es suprayectiva, existe $v\in V$ tal que $T(v)=w$ y como $S$ es generador, existen $a_1,\ldots,a_n$ tales que $$a_1v_1+\ldots+a_nv_n=v.$$ Aplicando $T$ en ambos lados, abriendo las sumas y sacando escalares obtenemos que $$a_1T(v_1)+\ldots+a_nT(v_n)=T(v)=w.$$ Así, todo elemento de $W$ se puede escribir como combinación lineal de elementos de $T(S)$, como queríamos.

Finalmente, supongamos que $T$ es biyectiva y $S$ es base. Como $T$ es inyectiva y $S$ linealmente independiente, entonces $T(S)$ es linealmente independiente. Como $T$ es suprayectiva y $S$ generador, entonces $T(S)$ es generador. Así, $T(S)$ es base.

$\square$

Una consecuencia fudamental del resultado anterior es que si $V$ y $W$ son espacios de dimensión finita y existe una transformación lineal inyectiva $T:V\to W$, entonces $\dim(V)\leq \dim(W)$. En efecto, si $B$ es base de $V$ y $T$ es inyectiva, entonces $T(B)$ es linealmente independiente en $W$ y sabemos que $W$ tiene a lo más $\dim(W)$ vectores linealmente independientes, así que $\dim(V)=|B|=|T(B)|\leq \dim(W)$. De manera similar, si existe una transformación lineal $T:V\to W$ suprayectiva, entonces $\dim(V)\geq \dim(W)$. Demuestra esto. ¿Qué pasa con las dimensiones si existe una transformación lineal biyectiva entre $V$ y $W$?

¿Cuándo una transformación lineal es inyectiva?

El teorema anterior también sugiere que es importante saber cuándo una transformación lineal es inyectiva, suprayectiva o ambas. Resulta que en el caso de la inyectividad hay un criterio que nos ayuda.

Proposición. Sean $V$ y $W$ espacios vectoriales. Una transformación lineal $T:V\to W$ es inyectiva y si sólo si el único vector $v$ de $V$ tal que $T(v)=0$ es el vector $v=0$. En otras palabras $T$ es inyectiva si y sólo si $\ker(T)=\{0\}$.

Demostración. Sean $V$ y $W$ espacios vectoriales y $T:V\to W$ una transformación lineal. Recordemos que sabemos que $T(0)=0$.

Si $T$ es inyectiva y $T(x)=0$, entonces $T(x)=T(0)$ y por inyectividad $x=0$, de modo que $x$ es el único vector que va a $0$ bajo $T$.

Si el único vector que bajo $T$ va a $0$ es el $0$ y tenemos que $T(x)=T(y)$, entonces usando que $T$ es lineal tenemos que $0=T(y)-T(x)=T(y-x)$. Así, por hipótesis $y-x=0$, es decir, $x=y$. Con esto queda mostrado que $T$ es inyectiva.

$\square$

Transformaciones lineales en bases dan toda la información

Conociendo los valores de una transformación lineal en algunos vectores, es posible determinar el valor de la transformación en otros vectores que son combinación lineal de los primeros. Considera el siguiente ejemplo.

Problema. La transformación lineal $T:M_2(\mathbb{R})\to\mathbb{R}^2$ cumple que $T\begin{pmatrix}
1 & 1\\
0 & 0
\end{pmatrix}=(1,0)$, $T\begin{pmatrix}
0 & 1 \\
0 & 1
\end{pmatrix}=(0,-1)$, $T\begin{pmatrix}
0 & 0\\
1 & 1
\end{pmatrix}=(-1,0)$ y $T\begin{pmatrix}
1 & 0\\
1 & 0
\end{pmatrix}=(0,1)$. Determina el valor de $T\begin{pmatrix} 3 & 3\\ 3 & 3\end{pmatrix}$.

Intenta resolver el problema por tu cuenta antes de ver la solución. Para ello, intenta poner a la matriz $\begin{pmatrix} 3 & 3\\ 3 & 3\end{pmatrix}$ como combinación lineal de las otras matrices y usar que $T$ es lineal.

Solución. Sean $A$, $B$, $C$ y $D$ las matrices de las cuales conocemos cuánto vale $T$ en ellas y $E$ la matriz con puros $3$’s. Queremos determinar el valor de $T(E)$. Notemos que $E=\frac{3}{2}(A+B+C+D)$. Como $T$ es transformación lineal, tenemos que

\begin{align*}
T(E)&=\frac{3}{2}(T(A)+T(B)+T(C)+T(D))\\
&=\frac{3}{2}((1,0)+(0,-1)+(-1,0)+(0,1))\\
&=(0,0).
\end{align*}

$\square$

En este problema lo que sirvió para encontrar el valor de $T(E)$ fue poner a la matriz $E$ como combinación lineal de las matrices $A,B,C,D$. De hecho, para cualquier matriz que sea combinación lineal de las matrices $A,B,C,D$, pudiéramos haber hecho lo mismo.

A partir de esta observación, podemos intuir que al conocer el efecto de transformaciones lineales en bases, podemos saber qué le hacen a cada elemento del espacio vectorial. El siguiente teorema enuncia esto de manera formal y dice un poco más.

Teorema. Sean $V$, $W$ espacios vectoriales, $B=\{v_1,v_2,\ldots,v_n\}$ una base de $V$ y $w_1,w_2,\ldots, w_n$ vectores cualesquiera de $W$. Entonces, existe una y sólo una transformación lineal $T:V\to W$ tal que $$T(v_1)=w_1,\quad T(v_2)=w_2, \quad \ldots, \quad T(v_n)=w_n.$$

Demostración. Probemos primero la parte de existencia. Como $B$ es base, cualquier vector $v$ de $V$ se puede escribir como $$a_1v_1+a_2v_2+\ldots+a_nv_n.$$ Construyamos la función $T:V\to W$ tal que $$T(v)=a_1w_1+a_2w_2+\ldots+a_nw_n.$$

Como para cada $i=1,\ldots,n$ tenemos que la combinación lineal de $v_i$ en términos de $B$ es $v_i=1\cdot v_i$, tenemos que $T(v_i)=1\cdot w_i=w_i$, que es una de las cosas que queremos. La otra que queremos es que $T$ sea lineal. Mostremos esto. Si $$v=a_1v_1+a_2v_2+\ldots+a_nv_n$$ y $$w=b_1v_1+b_2v_2+\ldots+b_nv_n,$$ entonces $$v+w=(a_1+b_1)v_1+
(a_2+b_2)v_2+\ldots+ (a_n+b_n)v_n,$$ y por definición $$T(v+w)=(a_1+b_1)w_1+ (a_2+b_2)w_2+\ldots+ (a_n+b_n)w_n.$$ Notemos que el lado derecho es igual a $T(v)+T(w)$, de modo que $T$ abre sumas. De manera similar se puede mostrar que $T$ saca escalares.

Esbocemos ahora la demostración de la unicidad. Supongamos que $T$ y $T’$ son transformaciones lineales de $V$ a $W$ tales que $T(v_i)=T'(v_i)=w_i$ para toda $i=1,\ldots,n$. Tenemos que mostrar que $T(v)=T'(v)$ para toda $v$. Para ello procedemos como en el problema antes de este teorema: escribimos a $v$ como combinación lineal de elementos de $B$. Esto se puede hacer de una única forma. El valor de $T(v)$ a su vez depende únicamente de $w_1,\ldots,w_n$ y de la los coeficientes en combinación lineal. El de $T'(v)$ también. Por lo tanto son iguales.

$\square$

Una consecuencia del teorema anterior, en la que no es necesario enunciar a las imágenes de la base, es la siguiente.

Corolario. Sean $V$ y $W$ espacios vectoriales, $B$ una base de $V$, y $T$ y $T’$ transformaciones lineales de $V$ a $W$. Si $T(v)=T'(v)$ para toda $v\in B$, entonces $T(v)=T'(v)$ para toda $v\in V$.

Más adelante…

Las propiedades que demostramos en esta entrada se usan con tanta frecuencia que muchas veces se aplican sin siquiera detenerse a argumentar por qué son válidas. Por esta razón, es importante que te familiarices con ellas. Otra ventaja de conocerlas a profundidad es que muchas veces ayudan a dar demostraciones sencillas o elegantes para algunos problemas. Finalmente, los hechos que aquí mostramos los usaremos prácticamente sin demostración en las siguientes entradas, en donde desarrollaremos la teoría de la forma matricial de transformaciones lineales.

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Encuentra qué le hace al vector $(7,3)$ una transformación lineal $T:\mathbb{R}^2\to \mathbb{R}$ tal que $T(2,1)=20$ y $T(7,2)=5$.
  • Determina si las matrices $A,B,C,D$ del problema de la entrada son una base para $M_2(\mathbb{R})$. Si no son una base, ¿cuál es la dimensión del subespacio que generan?
  • En el último teorema se afirma que la función que construimos saca escalares. Muestra esto.
  • De ese mismo teorema, escribe los detalles de que dicha función es única.
  • Demuestra el corolario enunciado en la entrada.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104721 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM»

Seminario de Resolución de Problemas: Introducción a principio de inducción

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

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.