Archivo de la etiqueta: lineas

Álgebra Lineal I: Ortogonalidad, hiperplanos y ecuaciones lineales

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En entradas anteriores hablamos de formas lineales, del espacio dual y de ortogonalidad. Con la teoría que hemos desarrollado en esas entradas, podemos cosechar uno de los hechos más importantes para espacios vectoriales de dimensión finita $n$: todos los subespacios se pueden obtener a partir de intersectar hiperplanos, es decir, subespacios de dimensión $n-1$. El objetivo de esta entrada es dar las definiciones necesarias para enunciar y demostrar este resultado formalmente.

Hiperplanos

Antes de demostrar el resultado mencionado en la introducción, tomaremos un poco de intuición geométrica de $\mathbb{R}^3$.

En $\mathbb{R}^3$ tenemos sólo un subespacio de dimensión $0$, que es $\{(0,0,0)\}$, un punto. Para obtener un subespacio de dimensión $1$, tenemos que tomar un vector $v\neq 0$ y considerar todos los vectores $rv$ con $r$ en $\mathbb{R}$. Esto corresponde geométricamente a una línea por el origen, con la misma dirección que $v$. En otras palabras, los subespacios de dimensión $1$ son líneas por el origen.

¿Quiénes son los subespacios de dimensión $2$? Debemos tomar dos vectores linealmente independientes $u$ y $v$ y considerar todas las combinaciones lineales $au+bv$ de ellos. Es más o menos fácil convencerse de que obtendremos al plano que pasa por $u$, $v$ y el $(0,0,0)$. Es decir, los subespacios de dimensión $2$ de $\mathbb{R}^3$ son planos por el origen.

Esto motiva la siguiente definición.

Definición 1. Sea $V$ un espacio vectorial de dimensión finita $n$. Un hiperplano de $V$ es un subespacio de dimensión $n-1$.

Ejemplo. El subespacio $U=\mathbb{R}_5[x]$ de $V=\mathbb{R}_6[x]$ es un hiperplano. Esto es ya que $U$ es de dimesión $6$ y $V$ es de dimensión $7$. Sin embargo, aunque $U$ también es un subespacio de $W=\mathbb{R}_7[x]$, no se cumple que $U$ sea hiperplano de $W$ pues $W$ es de dimensión $8$ y $6\neq 8-1$.

Las matrices simétricas de $M_2(\mathbb{R})$ forman un subespacio $S$ de dimensión $3$ de $M_2(\mathbb{R})$, pues son de la forma $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$. De esta forma, $S$ es un hiperplano de $M_2(\mathbb{R})$. Sin embargo, el conjunto de matrices simétricas de $M_n(\mathbb{R})$ no es un hiperplano ni para $n=1$, ni para $n\geq 3$.

$\triangle$

Los hiperplanos nos pueden ayudar a obtener subespacios. De hecho, veremos que en el caso de dimensión finita nos ayudan a obtener a todos los subespacios. Para continuar construyendo la intuición, notemos que en $\mathbb{R}^3$ los hiperplanos son simplemente los planos por el origen y que:

  • Podemos obtener a cualquier plano por el origen como intersección de planos por el origen: simplemente lo tomamos a él mismo.
  • Podemos obtener a cualquier línea por el origen como la intersección de dos planos distintos por el origen que la contengan. Por ejemplo, el eje $z$ es la intersección de los planos $xz$ y $yz$. En otras palabras: todo subespacio de dimensión $1$ de $\mathbb{R}^3$ se puede obtener como la intersección de dos hiperplanos de $\mathbb{R}^3$.
  • A $\{0\}$ lo podemos expresar como la intersección de los planos $xy$, $yz$ y $xz$, osea, al único espacio de dimensión cero lo podemos expresar como intersección de $3$ hiperplanos.

Ya obtenida la intuición, lo que veremos a continuación es que el resultado anterior en realidad es un fenómeno que sucede en cualquier espacio vectorial de dimensión finita. Así, nos enfocaremos en entender las definiciones del siguiente teorema, y demostrarlo.

Teorema. Sea $V$ un espacio vectorial de dimensión finita $n$.

  • Todo subespacio $W$ de $V$ de dimensión $m$ es la intersección de $n-m$ hiperplanos de $V$ linealmente independientes.
  • Toda intersección de $n-m$ hiperplanos de $V$ linealmente independientes es un subespacio vectorial de dimensión $m$.

Los hiperplanos son subespacio y la definición de independencia lineal que tenemos es para vectores. Pero el teorema anterior habla de «hiperplanos linealmente independientes». ¿A qué se refiere esto? Como veremos más adelante, a cada hiperplano se le puede asignar de manera natural un elemento del espacio dual de $V$.

Recordatorio de espacio ortogonal

En la entrada anterior mostramos el siguiente resultado:

Teorema (teorema de dualidad). Sea $V$ un espacio vectorial de dimensión finita sobre $F$ y $W$ un subespacio de $V$ (o de $V^\ast)$. Entonces $$\dim W + \dim W^\bot = \dim V.$$

Además, obtuvimos como corolario lo siguiente:

Corolario. Si $V$ es un espacio vectorial de dimensión finita sobre un campo $F$ y $W$ un subespacio de $V$ (o de $V^\ast$), entonces $(W^\bot)^\bot=W$.

Usaremos estos resultados para dar una definición alternativa de hiperplanos, para entender a los subespacios de dimensión $n-1$ y para mostrar el teorema principal de esta entrada.

Subespacios de dimensión $n-1$ y definición alternativa de hiperplanos

Tomemos un espacio vectorial $V$ de dimensión finita $n$. Un caso especial, pero muy importante, del teorema de dualidad es cuando $W$ es un subespacio de $V^\ast$ de dimensión $1$, es decir, cuando $W$ está generado por una forma lineal $l\neq 0$. En este caso, $W^\bot$ es un subespacio de $V$ y por el teorema de dualidad, es de dimensión $n-1$.

De manera inversa, si $W$ es un subespacio de $V$ de dimensión $n-1$, por el teorema de dualidad tenemos que $W^\bot$ es de dimensión $1$, así que hay una forma lineal $l\neq 0$ que lo genera. Por el corolario, $W=(W^\bot)^\bot$, que en otras palabras quiere decir que $W=\{v\in V: l(v)=0\}.$ En resumen:

Proposición. Un subespacio $W$ de un espacio de dimensión finita $d$ tiene dimensión $d-1$ si y sólo si es el kernel de una forma lineal $l\neq 0$ de $V$.

Ejemplo 1. Considera la forma lineal $\text{ev}_0$ en el espacio vectorial $V=\mathbb{C}_n[x]$ de polinomios con coeficientes complejos y grado a lo más $n$. Los polinomios $p$ tales que $\text{ev}_0(p)=0$ son exactamente aquellos cuyo término libre es $0$. Este es un subespacio vectorial de $V$ de dimensión $n=\dim V – 1$, pues una base para él son los polinomios $x, x^2, \ldots, x^n$.

$\triangle$

Problema. Considera el espacio vectorial $V=M_{2,3}(\mathbb{R})$. Considera $W$ el subconjunto de matrices cuya suma de entradas en la primer columna es igual a la suma de entradas de la segunda columna. Muestra que $W$ es un subespacio de dimensión $5$ y escríbelo como el kernel de una forma lineal.

Solución. Mostrar que $W$ es un subespacio de $V$ es sencillo y se queda como tarea moral. Se tiene que $W$ no puede ser igual a todo $V$ pues, por ejemplo, la matriz $\begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix}$ no está en $W$, así que $\dim W\leq 5$.

Las matrices $\begin{pmatrix} 1 & 1 & 0\\ 0 & 0 & 0 \end{pmatrix}$, $\begin{pmatrix} 1 & 1 & 1\\ 0 & 0 & 0 \end{pmatrix}$, $\begin{pmatrix} 1 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix}$, $\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}$, $\begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 0 \end{pmatrix}$ son linealmente independientes y están en $W$, así que $\dim W\geq 5$, y junto con el párrafo anterior concluimos que $\dim W = 5$.

Finalmente, tomemos la forma lineal $$l\begin{pmatrix} a & b & c\\ d& e& f\end{pmatrix}=a+d-b-e.$$ Tenemos que una matriz está en el kernel de $l$ si y sólo si $a+d-b-e=0$, si y sólo si $a+d=b+e$, es decir, si y sólo si las entradas de la primer columna tienen la misma suma que las de la segunda. Así, $W=\ker l$.

$\square$

La proposición anterior nos permite dar una definición alternativa de hiperplano y hablar de hiperplanos linealmente independientes.

Definición 2. Sea $V$ un espacio vectorial. Un hiperplano es el kernel de una forma lineal $l\neq 0$ en $V^\ast$. Una familia de hiperplanos es linealmente independiente si sus formas lineales correspondientes son linealmente independientes en $V^\ast$.

Observa además que la definición anterior también sirve para espacios vectoriales de dimensión infinita, pues nunca hace referencia a la dimensión que debe tener un hiperplano.

Ejemplo 2. El conjunto de funciones continuas $f$ en el intervalo $[0,1]$ tales que $$\int_0^1 f(x) \, dx = 0$$ son un subespacio $W$ de $\mathcal{C}[0,1]$. Este subespacio es un hiperplano pues es el kernel de la forma lineal $I$ tal que $$I(f)=\int_0^1 f(x)\, dx.$$

$\square$

No mencionaremos más de espacios de dimensión infinita en esta entrada.

Escribiendo subespacios como intersección de hiperplanos

Ya podemos entender el teorema principal de esta entrada y demostrarlo. Lo enunciamos nuevamente por conveniencia.

Teorema 2. Sea $V$ un espacio vectorial de dimensión finita $n$.

  • Todo subespacio $W$ de $V$ de dimensión $m$ es la intersección de $n-m$ hiperplanos de $V$ linealmente independientes.
  • Toda intersección de $n-m$ hiperplanos de $V$ linealmente independientes es un subespacio vectorial de dimensión $m$.

Demostración. Tomemos un espacio vectorial $V$ de dimensión finita $n$ y un subespacio $W$ de dimensión $m$. Por el teorema de dualidad, la dimensión de $\dim W^\bot$ es $n-m$. Tomemos una base $B=\{l_1,l_2,\ldots,l_{n-m}\}$ de $W^\bot$. Por el corolario al teorema de dualidad, podemos expresar a $W$ como $$W=(W^\bot)^\bot=\{v\in V: l_1(v)=\ldots=l_{n-m}(v)=0\}.$$

Si definimos $L_i=\{v\in V: l_i(v)=0\}$, por la proposición de la sección anterior tenemos que cada $L_i$ es un hiperplano de $V$. Además, $$W=L_1\cap \ldots\cap L_{n-m}.$$ Como los $l_i$ son linealmente independientes, con esto logramos expresar a $W$ como intersección de $n-m$ hiperplanos linealmente independientes.

Probemos ahora la segunda parte de la proposición. Tomemos el conjunto $S=\{l_1,\ldots,l_{n-m}\}$ de formas linealmente independientes que definen a los hiperplanos. Un vector $v$ está en la intersección de todos estos hiperplanos si y sólo si $l_1(v)=\ldots=l_{n-m}(v)=0$, si y sólo si está en $S^\bot=\text{span}(S)^\bot$. Es decir, la intersección de los hiperplanos es precisamente el subespacio $\text{span}(S)^\bot$. Como $S$ es linealmente independiente, tenemos que $ \text{span}(S)$ es de dimensión $n-m$, de modo que por el teorema de dualidad, $\dim \text{span}(S)^\bot = n-(n-m)=m$. Esto muestra lo que queremos.

$\square$

Algunos problemas prácticos

Si tenemos un espacio $V$ de dimensión finita $n$, un subespacio $W$ de dimensión finita $m$ y queremos encontrar de manera práctica la expresión de $W$ como intersección de hiperplanos de $V$, podemos hacer el siguiente procedimiento:

  • Determinamos una base $l_1,\ldots,l_{n-m}$ para $W^\bot$ (la cual consiste de formas lineales de $V^\ast$). Esto lo podemos hacer con los pasos que mencionamos en la entrada anterior.
  • Definimos $L_i=\{v\in V: l_i(v)=0\}$.
  • Tendremos que $W$ es la intersección de los $L_i$.

Una última observación es que cada $L_i$ está definido por una ecuación lineal. Esto nos permite poner a cualquier subespacio como el conjunto solución a un sistema lineal. Esto lo cual podemos ver de forma práctica de la siguiente manera:

  • Tomamos una base $e_1,\ldots,e_n$ de $V$.
  • Tomemos un vector $v=a_1e_1+\ldots+a_ne_n$ que queremos determinar si está en $W$. Para ello, debe estar en cada $L_i$.
  • Cada $L_i$ está definido mediante la ecuación $l_i(v)=0$ de modo que si $v$ está en $L_i$ sus coordenadas $a_1,\ldots,a_n$ en la base $e_1,\ldots,e_n$ deben satisfacer la ecuación lineal $$l_i(e_1)a_1+\ldots+l_i(e_n)a_n=0.$$
  • De esta forma, los vectores $v$ en $W$ son aquellos cuyas coordenadas en la base $e_1,\ldots, e_n$ satisfacen el sistema de ecuaciones obtenido de las ecuaciones lineales para cada $i$ del punto anterior.

Veremos algunos ejemplos de estos procedimientos en la siguiente entrada.

La receta anterior nos permite concluir la siguiente variante del teorema de esta entrada, escrito en términos de ecuaciones lineales.

Teorema. Sea $V$ un espacio vectorial de dimensión finita $n$ y $B$ una base de $V$.

  • Un subespacio $W$ de dimensión $m$ se puede definir mediante un sistema de ecuaciones lineales independientes que deben satisfacer las coordenadas de los vectores de $W$ escritos en la base $B$.
  • Aquellos vectores cuyas coordenadas en la base $B$ satisfacen un sistema de ecuaciones lineales independientes homogéneo, forman un subespacio de $V$ de dimensión $n-m$.

La moraleja de esta entrada es que podemos pensar que los sistemas de ecuaciones, las intersecciones de hiperplanos y los subespacios de un espacio vectorial de dimensión finita son «prácticamente lo mismo».

Más adelante…

A lo largo de esta entrada enunciamos las definiciones necesarias para llegar al teorema que mencionamos al inicio: para un espacio vectorial de dimension finita $n$, todos los subespacios se pueden obtener a partir de intersectar hiperplanos, es decir, subespacios de dimensión $n-1$.

En la siguiente entrada utilizaremos este resultado para resolver algunos ejercicios y veremos en acción este importante teorema.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  • Considera el plano $P$ en $\mathbb{R}^3$ que pasa por el origen y por los vectores $(1,1,1)$, $(0,2,0)$. Encuentra reales $a,b,c$ tales que $$P=\{(x,y,z): ax+by+cz = 0 \}.$$
  • En todos los ejemplos en los que se menciona que algo es subespacio, verifica que en efecto lo sea. En los que se menciona que un conjunto es base, también verifica esto.
  • Encuentra una base para el espacio de polinomios $p$ en $M_n(\mathbb{C})$ tales que $\text{ev}(1)(p)=0$.
  • Sea $W$ el subconjunto de matrices de $V:=M_n(\mathbb{R})$ tal que la sumas de las entradas de todas las filas son iguales. Muestra que $W$ es un subespacio de $V$. Determina la dimensión de $W$ y exprésalo como intersección de hiperplanos linealmente independientes.
  • ¿Qué sucede cuando intersectas hiperplanos que no corresponden a formas linealmente independientes? Más concretamente, supongamos que tienes formas lineales $l_1,\ldots,l_m$ de $F^n$. Toma $B=\{e_1,\ldots,e_n\}$ la base canónica de $F^n$. Considera la matriz $A=[l_i(e_j)]$. ¿Qué puedes decir de la dimensión de la intersección de los hiperplanos correspondientes a los $l_i$ en términos del rango de la matriz $A$?

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.