Archivo de la etiqueta: sucesiones

Álgebra Lineal I: Subespacios vectoriales

Introducción

En la entrada anterior dimos la definición de espacio vectorial y vimos varios ejemplos de espacios vectoriales. Ahora hablaremos de subespacios vectoriales o simplemente, subespacios. A grandes rasgos, podemos pensar a un subespacio como un subconjunto de un espacio vectorial V que también es un espacio vectorial con las mismas operaciones de V.

Definición de subespacios vectoriales y primeras consecuencias

Definición. Sea V un espacio vectorial sobre un campo F. Un subespacio vectorial de V, o simplemente un subespacio de V, es un subconjunto no vacío W de V cerrado bajo las operaciones de suma vectorial y multiplicación escalar de V. En otras palabras, W es un subespacio de V si se cumplen las siguientes dos propiedades:

  1. (Cerradura de la suma vectorial) Para cualesquiera u y v elementos de W, se cumple que u+v está en W.
  2. (Cerradura de la multiplicación por escalar) Para cualquier escalar c en F y vector v en W se cumple que cv está en W.

En la entrada anterior ya vimos un ejemplo. Si tenemos un campo F y nos fijamos el espacio vectorial F[x] de polinomios, entonces para cualquier entero n el subconjunto F_n[x] de F[x] de polinomios de grado a lo más n es cerrado bajo la suma de polinomios y bajo el producto escalar. De esta forma, F_n[x] es un subespacio de F[x]. Más abajo veremos muchos ejemplos de subespacios, pero primero nos enfocaremos en algunas consecuencias de la definición.

Observación. Se cumple todo lo siguiente:

  1. Si W es un subespacio de un espacio vectorial V, entonces W debe tener al vector 0 de V (es decir, la identidad aditiva de la suma vectorial). Esto se debe a que W es no vacío, así que tiene por lo menos un elemento v. Si tomamos al 0 de F y usamos la propiedad (2) de subespacio con 0 y v obtenemos que 0v=0 está en W.
  2. Si W es un subespacio de un espacio vectorial V y v está en W, entonces -v también. Esto se debe a que por la propiedad (2) de subespacio tenemos que (-1)v=-v está en W.
  3. Si V es un espacio vectorial sobre F y W es un subespacio de V, entonces W también es un espacio vectorial sobre F con las mismas operaciones que V. Por un lado, el neutro e inversos aditivos existen por los dos incisos anteriores. Para el resto de las propiedades, se usa que se cumplen para elementos de V y por lo tanto también para los de W (pues es un subconjunto).
  4. Si W_1 y W_2 son dos subespacios de un espacio vectorial V, entonces la intersección W_1\cap W_2 también lo es.

\square

La primera propiedad nos puede ayudar en algunas ocasiones (no siempre) a darnos cuenta rápidamente si un subconjunto no es subespacio vectorial: si no tiene al vector 0, entonces no es subespacio.

La tercera propiedad tiene una consecuencia práctica muy importante: para mostrar que algo es un espacio vectorial, basta con mostrar que es un subespacio de algo que ya sabemos que es un espacio vectorial.

Problema. Muestra que \mathcal{C}[0,1], el conjunto de funciones continuas de [0,1] a \mathbb{R}, es un espacio vectorial sobre \mathbb{R} con las operaciones de suma de funciones y multiplicación por escalar.

Solución. En la entrada anterior vimos que el conjunto V de funciones de [0,1] a los reales es un espacio vectorial sobre \mathbb{R} con las operaciones de suma de funciones y multiplicación escalar. El conjunto \mathcal{C}[0,1] es un subconjunto de V.

Por argumentos de cálculo, la suma de dos funciones continuas es una función continua. Así mismo, al multiplicar una función continua por un real obtenemos de nuevo una función continua. De esta forma, \mathcal{C}[0,1] es un subespacio de V.

Por la observación (3) de la discusión previa, obtenemos que \mathcal{C}[0,1] es un espacio vectorial sobre \mathbb{R} con las operaciones de suma de funciones y multiplicación por escalar.

\square

Definiciones alternativas de subespacios vectoriales

Algunos textos manejan definiciones ligeramente distintas a la que nosotros dimos. Sin embargo, todas ellas son equivalentes.

Proposición. Sea V un espacio vectorial sobre el campo F y W un subconjunto de V. Los siguientes enunciados son equivalentes.

  1. W es un subespacio de V de acuerdo a nuestra definición.
  2. Para cualesquiera vectores u y v en W y escalares a y b en F, se tiene que au+bv está en W.
  3. Para cualesquiera vectores u y v en W y cualquier escalar c en F se tiene que cu+v está en W.

Demostración. (1) implica (2). Supongamos que W es un subespacio de V. Tomemos vectores u,v en W y escalares a,b en F. Como W es cerrado bajo producto escalar, se tiene que au está en W. De manera similar, bv está en W. Como W es cerrado bajo sumas, se tiene que au+bv está en W.

(2) implica (3). Supontamos que W satisface (2) y tomemos u,v en W y cualquier escalar c en F. Tomando a=c y b=1 en (2), tenemos que cu+1v=cu+v está en W.

(3) implica (1). Supongamos que W satisface (3). Hay que ver que W es cerrado bajo sumas y producto escalar. Si tomamos u y v en W y al escalar c=1 de F, por (3) obtenemos que cu+v=1u+v=u+v está en W, lo cual muestra la cerradura de la suma. Si tomamos cualquier escalar c y al vector w=0, entonces por (3) se tiene que cu+w=cu+0=cu está en W. Esto muestra la cerradura bajo producto escalar.

\square

La consecuencia práctica de la proposición anterior es que basta verificar (2) o (3) para garantizar que W es un subespacio.

Problema. Considera V el espacio vectorial de matrices en M_n(F). Muestra que el subconjunto W de matrices simétricas forman un subespacio de V.

Solución. Lo demostraremos probando el punto (3) de la proposición. Sea c un escalar en F y sean A y B matrices en W, es decir, tales que ^tA=A y ^tB = B. Debemos mostrar que cA+B está en W, es decir, que ^t(cA+B)=cA+B. Usando propiedades de la transpuesta y la hipótesis sobre A y B tenemos que:

    \[^t(cA+B) = c \ ^tA+ \ ^tB = cA + B.\]

Con esto termina la demostración.

\square

Más ejemplos de subespacios vectoriales

A continuación presentamos más ejemplos de subespacios vectoriales. En cada ejemplo damos un espacio vectorial y un subconjunto W. Para cada uno de los casos, piensa por qué la suma de dos elementos de W es de nuevo un elemento de W y por qué el producto de un escalar por un elemento de W es un elemento de W. También puedes usar la última proposición para probar ambas cosas simultáneamente.

  • Si tomamos M_2(\mathbb{R}), el subconjunto W de matrices que cumplen que la suma de entradas en su diagonal principal es igual a 0 es un subespacio.
  • En el espacio vectorial F^4, el subconjunto W de vectores cuya primera y tercer entrada son iguales a 0 forman un subespacio.
  • Las funciones acotadas del intervalo [-3, 3] a \mathbb{R} forman un subconjunto W que es un subespacio de las funciones del intervalo [-3,3] a \mathbb{R}.
  • El subconjunto W de vectores (x,y,z) de \mathbb{R}^3 tales que

        \[\begin{cases}x+y+z &= 0\\ x+ 2y + 3z &= 0 \end{cases}\]

    es un subespacio de \mathbb{R}^3.
  • Si tomamos W=\mathbb{R}_3[x], entonces este es un subespacio de \mathbb{R}_4[x].
  • Si tomamos W=\mathbb{R}_4[x], entonces este es un subespacio de \mathbb{R}_5[x].
  • El subconjunto W de funciones diferenciables de [0,10] a \mathbb{R} tales que su derivada evaluada en 7 es igual a 0 es un subespacio del espacio de funciones continuas de [0,10] a \mathbb{R}.
  • Las matrices triangulares superiores de M_n(F) forman un subespacio W del espacio M_n(F). Las matrices triangulares inferiores también. Como la intersección de estos subespacios es el conjunto de matrices diagonales, obtenemos que las matrices diagonales también son un subespacio (aunque claro, esto también se puede probar directamente de la definición).

Ejemplos de subconjuntos que no son subespacios vectoriales

Aunque ya vimos muchos ejemplos de subespacios, resulta que en realidad es un poco raro que un subconjunto de un espacio vectorial sea un subespacio. Los ejemplos de subconjuntos que no son subespacios vectoriales abundan. Veamos algunos y qué tipo de cosas pueden salir mal.

  • El subconjunto W=\{(x,y,z): x^2+y^2+z^2=1\} no es un subespacio de \mathbb{R}^3. Podemos dar el siguiente argumento: ya demostramos que un subespacio debe tener al vector cero. En este caso, W debería tener a (0,0,0) para ser subespacio. Pero 0^2+0^2+0^2=0\neq 1. Así, (0,0,0) no está en W y por lo tanto W no es subespacio.
  • Alternativamente, en el ejemplo anterior podemos ver que (1,0,0) está en W, pero 2(1,0,0)=(2,0,0) no.
  • El subconjunto W=\{(0,0), (1,2), (-1,2)\} de \mathbb{R}^2 no es un subespacio, pues (1,2) está en W. Tomando u=(1,2) y v=(1,2), vemos que W no es cerrado bajo sumas pues (1,2)+(1,2)=(2,4) no está en W.
  • Las matrices del subconjunto GL_n(F) de M_n(F), es decir, las matrices invertibles, no conforman un subespacio. Por un lado, ya vimos que el neutro aditivo de la suma debe estar en un subespacio, pero la matriz O_n no es invertible, así que no está en GL_n(F).
  • El subconjunto W de funciones f:[-3,3]\to \mathbb{R} diferenciables tales que su derivada en 0 es igual a 2 no es un subespacio de las funciones continuas de [-3,3] a \mathbb{R}. Hay muchas formas de verlo. Podemos darnos cuenta que f(x)=x^2+2x es una de las funciones en W pues f'(x)=2x+2 y f'(0)=2. Sin embargo, 3f no está en W.
  • El subconjunto W de polinomios de \mathbb{R}[x] con coeficientes no negativos no es un subespacio de \mathbb{R}[x]. El polinomio 0 sí está en W y la suma de cualesquiera dos elementos de W está en W. Sin embargo, falla la multiplicación escalar pues x está en W, pero (-1)x=-x no.
  • La unión del eje X, el eje Y y el eje Z de \mathbb{R}^3 es un subconjunto W de \mathbb{R}^3 que no es un subespacio. Cualquier producto escalar queda dentro de W, pero la suma no es cerrada.

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.

  • Demuestra que los siguientes conjuntos W son subespacios del espacio vectorial indicado.
    • El subconjunto W de vectores (w,x,y,z) de \mathbb{C}^4 tales que w+x+y+z=0.
    • La colección W de funciones continuas f:[0,1]\to \mathbb{R} tales que \int_0^1 f(x) \, dx = 0 es un subespacio del espacio de funciones de [0,1] a \mathbb{R}.
    • W=\left\{\begin{pmatrix} a+b & b\\ -b & c+b \end{pmatrix}: a,b,c \in \mathbb{R} \right\} es un subespacio de las matrices en M_2(\mathbb{R}).
  • Demuestra que los siguientes conjuntos W no son subespacios del espacio vectorial indicado.
    • El subconjunto W de vectores (x,y) de \mathbb{R}^2 tales que xy\geq 0 no es un subespacio de \mathbb{R}^2.
    • El subconjunto W de matrices en M_{3,2}(F) cuyo producto de todas las entradas es igual a 0 no es un subespacio de M_{3,2}
    • Cuando W es un subconjunto finito y con al menos dos polinomios con coeficientes complejos y de grado a lo más 3, es imposible que sea un subespacio de \mathbb{C}_3[x].
  • Sea V un espacio vectorial y n un entero positivo. Demuestra que si W_1, W_2, \ldots, W_n son subespacios de V, entonces la intersección

        \[W_1 \cap W_2 \cap \ldots \cap W_n\]

    también lo es.
  • Escribe por completo la demostración de que cualquier subespacio de un espacio vectorial es también un espacio vectorial con las mismas operaciones.
  • Demuestra que si V es un espacio vectorial, W es un subespacio de V y U es un subespacio de W, entonces U es un subespacio de V.

Más adelante…

En esta entrada definimos el concepto de subespacio de un espacio vectorial. En la siguiente hablaremos de algunas operaciones que se les puede hacer a los subespacios vectoriales para «combinarlos» y obtener más subespacios. Una operación muy imporante es la de suma de subespacios, que puede tener dos o más sumandos. La operación de suma de subespacios es particularmente especial cuando los subespacios están en posición de suma directa. Para irte dando una idea de qué quiere decir esto, dos subespacios están en posición de suma directa si su único elemento en común es el vector 0. El caso general de más subespacios se enuncia de forma distinta y también lo veremos en la siguiente entrada.

Entradas relacionadas

Seminario de Resolución de Problemas: Series geométricas

Introducción

En esta entrada y en otras subsecuentes, trataremos el tema de series aplicado a la resolución de problemas matemáticos. Recordemos que en entradas anteriores ya se estudiaron los conceptos de sucesiones. Para esta entrada aprovecharemos lo que hemos aprendido de sucesiones geométricas.

Series geométricas

Si consideramos una sucesión geométrica \{a_i\}_{i\in\mathbb{N}}, recordemos que se cumple que existe una razón r de tal manera que a_n=ra_{n-1}, expresado en el primer término, tenemos que a_n=r^{n}a_0. Ahora bien, nos interesará saber o conocer las suma de los elementos de una sucesión geométrica. A esta suma se le conoce como serie geométrica y puede realizarse considerando una cantidad finita de elementos de la sucesión, así como una cantidad infinita de elementos de la sucesión.

Si queremos obtener la serie geométrica de los primeros n+1 elementos de la sucesión \{a_i\}_{i\in\mathbb{N}}, tenemos lo siguiente

    \begin{equation*}\sum_{i=0}^n a_i=a_0+a_1+a_2 +a_3+\ldots+a_n.\end{equation*}

Al multiplicar ambos lados de la igualdad por la razón de la sucesión tenemos que

    \begin{equation*}\begin{align}\sum_{i=0}^n a_i&=a_0+a_1+a_2 +a_3+\ldots+a_n\\r\sum_{i=0}^n a_i&=ra_0+ra_1+ra_2 +ra_3+\ldots+ra_n\\&=a_1+a_2+\ldots+a_{n+1}\end{equation*}

Y si calculamos r\sum_{i=0}^n a_i-\sum_{i=0}^n a_i, se cancelan todos los términos excepto el último de la primer suma, y el primero de la segunda. Obtenemos entonces:

    \begin{equation*}\begin{align*}r\sum_{i=0}^n a_i-\sum_{i=0}^n a_i&=a_{n+1}-a_0.\end{align*}\end{equation*}

Así,

    \begin{equation*}\sum_{i=0}^na_i=\frac{a_{n+1}-a_0}{r-1}=a_0\frac{r^{n+1}-1}{r-1}.\end{equation*}

Ahora bien, si tenemos la sucesión geométrica \{a_i\}_{i\in\mathbb{N}} y queremos calcular la serie infinita de todos sus elementos basta con que calculemos el límite cuando n\to \infty tiende a infinito de

    \[\sum_{i=0}^na_i=a_0\frac{r^{n+1}-1}{r-1}.\]

Supogamos que a_0\neq 0, pues en otro caso la suma de los términos es igual a 0. Si |r|>1, el numerador diverge y por lo tanto la serie también. Cuando r=1, la serie diverge pues cada sumando es igual a a_0\neq 0. Cuando r=-1, tenemos una serie de términos alternante que no converge, pues es, iteradamente, a_0,0,a_0,0,\ldots.

Por otro lado, si |r|<1, entonces r^{n+1}\to 0. En este caso, la serie converge a \frac{a_0}{1-r}.

Aplicación de series geométricas a áreas

Si consideramos la sucesión \{x^i\}_{i\in\mathbb{N}} tenemos que dicha sucesión está dada por \left\{1, x, x^2, x^3,\ldots\right\} la sucesión es geométrica, dado que la razón es r=x.

De acuerdo al análisis que hicimos arriba, la serie geométrica finita está dada por

    \begin{equation*}\sum_{i=0}^n x^i=(1)\frac{x^{n+1}-1}{x-1}=\frac{1-x^{n+1}}{1-x}\end{equation*}

A partir de aquí deducimos que la serie geométrica infinita está dada por

    \begin{equation*}\sum_{i=0}^{\infty} x^i=\lim_{n\to\infty}\frac{1-x^{n+1}}{1-x}=\frac{1}{1-x}\end{equation*}

solo si |x|< 1. En otro caso, la serie diverge.

\square

Un problema aplicado a la geometría

Consideremos la siguiente figura, en donde \triangle ABC es un triángulo equilatero y OA=16.


Imaginemos que la figura continúa internamente de manera infinita, resultando en una cantidad infinita de triángulos, todos ellos equiláteros. ¿Cuál sería la suma de las áreas de todos los triángulos?

Para ello, primero tendríamos que ver el área de cada triángulo como elemento de una sucesión, la cual parece que será geométrica.

Comencemos calculando el área del \triangle ABC. Para ello tenemos que determinar el valor de la altura. Notemos que CE es altura del triángulo, a su vez, CE=OC+OE. Como OC es radio de la circunferencia, tenemos que OC=16. Sólo falta determinar el valor del segmento OE.

Si nos fijamos en \triangle AOE, tenemos que es un triángulo rectángulo, además que AO es bisectriz del \angle A, así que \angle OAE=30^o. Como \sin30^o=OE/16=1/2 tenemos entonces que OE=8.

Por lo anterior, tenemos que que la altura del \triangle ABC está dada por h=24. De una manera similar podemos calcular la base del triángulo, la cual está dada por b=16\sqrt{3}. Así, el área del \triangle ABC es A_0=192\sqrt{3}.

El área del triángulo inscrito en el \triangle ABC es la cuarta parte de A_0, es decir A_1=\frac{1}{4}A_0. De manera sucesiva A_2=\frac{1}{4}A_1, A_3=\frac{1}{4}A_2, \ldots.

Si nos fijamos en la sucesión de las áreas de los triángulos\{A_i\}_{i\in\mathbb{N} tenemos que es geométrica de razón r=1/4.

De esta forma, la suma de las áreas de todos los triángulos es una serie geométrica dada por

    \begin{equation*}\begin{align*}\sum_{i=0}^{\infty} A_i&=\lim_{x\to\infty}(192\sqrt{3})\frac{1-(1/4)^{n+1}}{1-(1/4)}\\&=(192\sqrt{3})\frac{1}{1-(1/4)}=(192\sqrt{3})(4/3)\\&=256\sqrt{3}\end{align*}\end{equation*}

\square

Aplicación de series geométricas a números perfectos

Un número entero positivo n se dice que es perfecto si la suma de sus divisores sin incluir al mismo n da como resultado n. Por ejemplo, el número 6 es un número perfecto ya que sus divisores sin incluir al mismo 6 son 1, 2, 3 y su suma 1+2+3=6.

Ahora veamos un problema que relaciona a los números perfectos y a las series geométricas.

Problema: Sea n=2^{p-1}(2^p-1), donde 2^p-1 es primo. Prueba que n es un número perfecto.

Solución: Tenemos que todos los divisores de n sin contar al mismo n están conformados por la unión de las siguientes dos sucesiones finitas.

    \begin{equation*}\begin{align*}&\{2^i\}_{i=0}^{p-1}=1, 2, 2^2,...,2^{p-1}\\&\{(2^p-1)2^i\}_{i=0}^{p-2}=(2^p-1), 2^2(2^p-1), 2^3(2^p-1),..., 2^{p-2}(2^p-1)\end{align*}\end{equation*}

Si consideramos la suma de los elementos de cada sucesión

    \begin{equation*}\begin{align*}&\sum_{i=0}^{p-1}2^i=\frac{2^p-1}{2-1}=2^p-1\\&\sum_{i=0}^{p-2}2^i(2^p-1)=(2^p-1)\frac{2^p-1}{2-1}=(2^p-1)(2^{p-1}-1)\end{align*}\end{equation*}

Así la suma de todos los divisores de n sin incluir al propio n es

    \begin{align*}(2^p-1)+(2^p-1)(2^{p-1}-1)&=(2^p-1)(1+2^{p-1}-1)\\&=2^{p-1}(2^p-1)\\&=n.\end{align*}

Por lo tanto, tenemos que n es un número perfecto.

\square

Otro problema interesante

Problema: Una sucesión está definida por a_1=2 y a_n=3a_{n-1}+1, encuentra el valor de la suma

    \[a_1+a_2+a_3+\ldots+a_n.\]

Solución: Notemos que la sucesión que nos dan no es geométrica, dado que no es posible encontrar un número r que funcione como razón. Así que busquemos un patrón que aparezca al realizar las primeras sumas.

    \begin{align*}a_1&=2\\a_2&=3a_1+1\\&=3(2)+1\\a_3&=3a_2+1\\&=3(3(2)+1)+1\\&=3^2(2)+3+1\\a_4&=3a_3+1\\&=3(3^2(2)+3+1)+1\\&=3^3(2)+3^2+3+1\\a_5&=3a_4+1\\&=3(3^3(2)+3^2+3+1)\\&=3^4(2)+3^3+3^2+3+1.\end{align*}

De manera sucesiva, podemos conjeturar y mostrar por inducción que

    \begin{align*}a_n&=3^{n-1}(2)+3^{n-2}+\ldots+3+1\\&=3^{n-1}(2)+\frac{3^{n-1}-1}{2}\\&=\frac{5\cdot 3^{n-1}-1}{2}.\end{align*}



Así que

    \begin{align*}\sum_{i=1}^na_i&=\sum_{i=1}^n \frac{5\cdot 3^{i-1}-1}{2}\\&=\frac{1}{2}\sum_{i=1}^n 5\cdot 3^{i-1}-1\\&=\frac{1}{2}\left(5\cdot \frac{3^n-1}{2} - n\right).\end{align*}

\square

Más problemas

Puedes encontrar más problemas de series geométricas en la sección 5.2 del libro Problem Solving through Problems de Loren Larson.

Álgebra Superior II: El anillo de polinomios con coeficientes reales

Introducción

Estamos listos para la cuarta y última parte del curso, en donde construiremos el anillo de polinomios con coeficientes reales. Los elementos de este anillo son polinomios, los cuales se aparecen en numerosas áreas de las matemáticas. Tras su construcción, aprenderemos varias herramientas para trabajar con ellos.

En las tres primeras partes del curso ya trabajamos con otras estructuras algebraicas. Hasta ahora, hemos hablado de lo siguiente:

  • Naturales: Construimos a partir de teoría de conjuntos al conjunto \mathbb{N} de números naturales, sus operaciones y orden. De lo más relevante es que dentro de los naturales podemos hacer definiciones por recursión y pruebas por indución.
  • Enteros: Con \mathbb{N} construimos a los enteros \mathbb{Z}, sus operaciones y orden. Hablamos de divisibilidad y factorización. Esto dio pie a construir \mathbb{Z}_n, los enteros módulo n, junto con su aritmética. Aprendimos a resolver ecuaciones en \mathbb{Z} y sistemas de congruencias.
  • Racionales y reales: Mencionamos brevemente cómo se construye \mathbb{Q} a partir de \mathbb{Z} y cómo se construye \mathbb{R} a partir de \mathbb{Q}. Tanto \mathbb{R} como \mathbb{Q} son campos, así que ahí se pueden hacer sumas, restas, multiplicaciones y divisiones.
  • Complejos: A partir de \mathbb{R} construimos el campo \mathbb{C} de los números complejos. Definimos suma, multiplicación, inversos, norma y conjugados. Luego, desarrollamos herramientas para resolver varios tipos de ecuaciones en \mathbb{C}. Finalmente, construimos las funciones exponenciales, logarítmicas y trigonométricas.

Quizás a estas alturas del curso ya veas un patrón de cómo estamos trabajando. Aunque varias de estas estructuras ya las conocías desde antes, hay una primer parte importante que consiste en formalizar cómo se construyen. Luego, vimos cómo se definen las operaciones en cada estructura y qué propiedades tienen. Haremos algo muy parecido con los polinomios.

Intuición de los polinomios

La idea de esta entrada es llegar a los polinomios que ya conocemos, es decir, a expresiones como la siguiente:

    \[4+5x+\frac{7}{2}x^2-x^4+3x^5.\]

Lo que tenemos que formalizar es qué significa esa «x», y cómo le hacemos para sumar y multiplicar expresiones de este tipo.

Intuitivamente, lo que queremos ese que en la suma «se sumen términos del mismo grado» y que en el producto «se haga la distribución y se agrupen términos del mismo grado». Por ejemplo, queremos que la suma funcione así

    \begin{align*}(1+&x-x^2+3x^3)+(-7+3x+x^2+2x^3+x^4)\\&=(1-7)+(1+3)x+(-1+1)x^2+(3+2)x^3+(0+1)x^4\\&=-6+4x+0x^2+5x^4+x^4\\&=-6+4x+5x^3+x^4,\end{align*}

y que la multiplicación funcione así

    \begin{align*}(2&+3x)(5+x+x^2)\\&=2(5+x+x^2)+3x(5+x+x^2)\\&=(10+2x+2x^2)+(15x+3x^2+3x^3)\\&=10+(2+15)x+(2+3)x^2+3x^3\\&=10+17x+5x^2+3x^3.\end{align*}

El exponente más grande de una x puede ser tan grande como queramos, pero no se vale que los polinomios tengan una infinidad de términos. Así, queremos descartar cosas del estilo

    \[1+x+x^2+x^3+x^4+\ldots,\]

en donde sumamos indefinidamente.

Construcción de polinomios

Para construir polinomios formalmente, tenemos que elegir de dónde van a venir sus coeficientes. Puede ser \mathbb{Q}, \mathbb{R}, \mathbb{Z} o incluso \mathbb{Z}_7, digamos. Nosotros nos enfocaremos en construir los polinomios con coeficientes en \mathbb{R}, que tiene la ventaja de ser un campo. Algunas de las propiedades que probaremos se valen para cualquier elección de coeficientes, pero otras no. No profundizaremos en estas diferencias, pero es bueno que lo tengas en mente para tu formación matemática posterior.

Definición. Dado un conjunto X, una sucesión de elementos de X es una función a:\mathbb{N}\to X. Para n en \mathbb{N}, a a(n) usualmente lo denotamos simplemente por a_n, y a la sucesión a por \{a_n\}.

Definición. El soporte de una sucesión es el conjunto de naturales n tales que a_n\neq 0.

Podemos «visualizar» los primeros términos de una sucesión así:

    \[(a_0, a_1, a_2, a_3, a_4, a_5, \ldots),\]

en donde podemos poner tantos términos como queramos y los puntos suspensivos indican que «sigue y sigue». Por supuesto, usualmente esta visualización no puede guardar toda la información de la sucesión, pero puede ayudarnos a entenderla un poco mejor.

Ejemplo. Si tomamos la función identidad \text{id}:\mathbb{N}\to \mathbb{N}, obtenemos la sucesión

    \[(0,1,2,3,4,5,6,7,\ldots).\]

Al tomar la función a:\mathbb{N}\to \mathbb{Z} tal que a_n=(-1)^n, obtenemos la sucesión

    \[(1,-1,1,-1,1,-1,\ldots).\]

\square

Los polinomios son aquellas sucesiones de reales que «después de un punto tienen puros ceros».

Definición. Un polinomio con coeficientes reales es una sucesión \{a_n\} de reales tal que a_n\neq 0 sólo para una cantidad finita de naturales n.

En otras palabras, un polinomio es una sucesión con soporte finito. Si visualizamos a un polinomio como una sucesión, entonces es de la forma

    \[(a_0,a_1,a_2,a_3,a_4,a_5,\ldots),\]

en donde a partir de un punto ya tenemos puros ceros a la derecha. Por conveniencia, marcaremos ese punto con un \overline{0}.

Ejemplo. La sucesión

    \[\left(5,7,\frac{7}{2},0,-1,3,0,0,0,\ldots\right),\]

en la que después del 3 ya todos los términos son ceros, representa a un polinomio. Con la convención de arriba, podemos escribirlo como

    \[\left(5,7,\frac{7}{2},0,-1,3,\overline{0}\right).\]

Su soporte consiste de aquellas posiciones en las que la sucesión no es cero, que son 0,1,2,4,5.

La sucesión

    \[(1,-1,1,-1,1,-1,\ldots)\]

dada por a_n=(-1)^n no es un polinomio, pues podemos encontrar una infinidad de términos no cero.

\square

Para que las definiciones de la siguiente sección te hagan sentido, puedes pensar de manera informal que la sucesión

    \[(a_0, a_1, a_2, a_3, a_4, a_5, \ldots),\]

representa al polinomio

    \[a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+\ldots.\]

La última condición en la definición de polinomio es la que garantiza que «tenemos un número finito de sumandos».

Definición. Definimos al conjunto de polinomios con coeficientes reales como

    \[\mathbb{R}[x]:=\{ p: p \text{ es polinomio con coeficientes reales}\}.\]

La igualdad se polinomios de define término a término.

Definición. Sean a=\{a_n\} y b=\{b_n\} en \mathbb{R}[x]. Decimos que a=b si para todo natural se tiene a_n=b_n.

En las siguientes secciones definiremos las operaciones de suma y producto en \mathbb{R}[x].

Suma y producto de polinomios

Los polinomios se suman «entrada a entrada».

Definición. Dados dos polinomios a=\{a_n\} y b=\{b_n\} en \mathbb{R}[x], definimos su suma como el polinomio

    \[a+b:=\{a_n+b_n\},\]

o bien, en términos de sucesiones, como la sucesión a+b:\mathbb{N}\to \mathbb{R} tal que (a+b)(n)=a(n)+b(n).

Observa que nos estamos apoyando en la suma en \mathbb{R} para esta definición.

Ejemplo. Los polinomios

    \[\left(0,2,0,4,-1,\frac{2}{3},\overline{0}\right)\]

y

    \[\left(1,-2,-1,-4,-2,\overline{0}\right)\]

tienen como suma al polinomio

    \[\left(0+1,2-2,0-1,4-4,-1-2,\frac{2}{3}+0,0+0,\ldots\right),\]

que es

    \[\left(1,0,-1,0,-3,\frac{2}{3},\overline{0}\right).\]

\square

La suma de dos polinomios sí es un polinomio pues claramente es una sucesión, y su soporte se queda contenido en la union de los soportes de los sumandos.

La siguiente definición guarda la idea de que para multiplicar queremos distribuir sumandos y agrupar términos del mismo grado. Tiene sentido si piensas en la asociación intuitiva informal que discutimos al final de la sección anterior.

Definición. Dados dos polinomios a=\{a_n\} y b=\{b_n\} en \mathbb{R}[x], definimos su producto como el polinomio

    \[ab:=\{c_n\},\]

en donde c_n está dado por

    \[c_n:=\sum_{i+j=n} a_ib_j,\]

en otras palabras,

    \[c_n=a_0b_n+a_1b_{n-1}+\ldots+a_{n-1}b_1+a_nb_0.\]

Aquí nos estamos apoyando en la suma y producto en \mathbb{R} para definir la multiplicación de polinomios.

Una forma práctica de hacer el producto es mediante una tabla. En la primer fila ponemos al primer polinomio y en la primer columna al segundo. Las entradas interiores son el producto de la fila y columna correspondiente. Una vez que hacemos esto, la entrada c_j del producto es la suma de los elementos en la j-ésima «diagonal».

Ejemplo. Multipliquemos a los polinomios

    \[a=(3,-2,0,1,\overline{0})\]

y

    \[b=(0,2,7,\overline{0}).\]

Ponemos a a y b en la primer fila y columna respectivamente de la siguiente tabla:

3-201
0
2
7

Luego, en cada entrada interior de la tabla ponemos el producto de los coeficientes correspondientes:

3-201
03 \cdot 0-2 \cdot 00\cdot 01\cdot 0
23 \cdot 2-2 \cdot 20\cdot 21\cdot 2
73 \cdot 7-2 \cdot 70\cdot 71\cdot 7

Después, hacemos las operaciones:

3-201
00000
26-402
321-1407

Finalmente, para encontrar el coeficiente c_j del producto, hacemos la suma de las entradas en la j-ésima diagonal dentro de la tabla, es decir:

    \begin{align*}c_0&=0\\c_1&=6+0=6\\c_2&=21-4+0=17\\c_3&=-14+0+0=-14\\c_4&=0+2=2\\c_5&=7.\end{align*}

De esta forma, el polinomio producto es

    \[(0,6,17,-14,2,7,\overline{0}).\]

Es muy recomendable que notes que esto coincide con el producto (por ahora informal)

    \begin{align*}(3-&2x+x^3)(2x+7x^2)\\&=6x+17x^2-14x^3+2x^4+7x^5.\end{align*}

\square

El anillo de polinomios con coeficientes reales

Los polinomios y los enteros se parecen, en el sentido de que como estructura algebraica comparten muchas propiedades. La idea de esta sección es formalizar esta afirmación.

Teorema. El conjunto \mathbb{R}[x] con las operaciones de suma y producto arriba definidos forman un anillo.

Demostración. Por una parte, tenemos que mostrar que la suma es asociativa, conmutativa, que tiene neutro e inversos aditivos. Por otra parte, tenemos que mostrar que el producto es asociativo. Finalmente, tenemos que mostrar que se vale la ley distributiva.

Tomemos dos polinomios a=\{a_n\}, b=\{b_n\} y un natural n. El término n de a+b es a_n+b_n y el de b+a es b_n+a_n, que son iguales por la conmutatividad de la suma en \mathbb{R}. De manera similar, se muestra que la suma es asociativa.

El polinomio (\overline{0}) es la identidad de la suma. Esto es sencillo de mostrar y se queda como tarea moral. Además, si a=\{a_n\} es un polinomio, entonces \{-a_n\} es una sucesión con el mismo soporte (y por lo tanto finito), que cumple que

    \[\{a_n\}+\{-a_n\}=(0,0,0,\ldots)=(\overline{0}),\]

así que la suma tiene inversos aditivos.

Ahora probemos la asociatividad del producto. Tomemos tres polinomios a=\{a_n\}, b=\{b_n\}, c=\{c_n\} y un natural n. Hagamos el producto (ab)c. Para cada i, el i-ésimo término de ab es un cierto d_i dado por

    \[d_i = \sum_{k+l=i} a_k b_l.\]

El n-ésimo término de (ab)c es entonces

    \begin{align*}\sum_{i+j=n}d_ic_j &= \sum_{i+j=n}\sum_{k+l=i} a_kb_lc_j\\&=\sum_{k+l+j=n}a_kb_lc_j.\end{align*}

Un argumento análogo muestra que el n-esimo término de a(bc) es también

    \begin{align*}\sum{k+l+j=n}a_kb_lc_j,\end{align*}

lo cual muestra que la multiplicación es asociativa.

Lo último que nos queda por probar es la ley distributiva. Tomemos tres polinomios a=\{a_n\}, b=\{b_n\}, c=\{c_n\} y un natural n. Usamos las propiedades de las operaciones en \mathbb{R} para ver que el n-ésimo término de a(b+c) es

    \begin{align*}\sum_{i+j=n} a_i(b_j+c_j)&=\sum_{i+j=n} (a_ib_j+ a_i c_j)\\&=\sum_{i+j=n} a_ib_j + \sum_{i+j=n} a_ic_j.\end{align*}

A la derecha tenemos el n-ésimo término de ab sumado con el n-ésimo término de ac, así que coincide con el n-ésimo término de la suma ab+ac. Esto muestra que a(b+c) y ab+ac son iguales término a término y por lo tanto son iguales como polinomios.

\square

Como de costumbre, al inverso aditivo de un polinomio a le llamamos -a, y definimos a-b:=a+(-b).

Proposición. La multiplicación en \mathbb{R}[x] es conmutativa.

Demostración. Tomemos dos polinomios a=\{a_n\} y b=\{b_n\}. Tenemos que ver que ab y ba son iguales término a término. Tomemos entonces un natural n. El término c_n de ab es

    \[c_n=\sum_{i+j=n} a_ib_j,\]

y el término d_n de ba es

    \[d_n=\sum_{i+j=n} b_ia_j.\]

Por la conmutatividad de la suma y el producto en \mathbb{R}, tenemos que c_n=d_n.

\square

Proposición. La multiplicación en \mathbb{R}[x] tiene identidad.

Demostración. El polinomio (1,\overline{0}) es la identidad multiplicativa. Esto es sencillo de mostrar y se queda como tarea moral.

\square

Proposición. Si a y b son polinomios en \mathbb{R}[x] distintos del polinomio (\overline{0}), entonces su producto también.

Demostración. Para ello, tomemos el mayor natural m tal que a_m\neq 0 y el mayor natural n tal que b_n\neq 0. Estos existen pues a y b no son el polinomio (\overline{0}), y su soporte es finito.

Cualquier pareja de naturales k y l tales que k+l=m+n con k\leq m-1 cumple l\geq n+1. Así, si k+l=m+n tenemos que:

  • Si k\leq m-1, entonces b_l=0 y por lo tanto a_kb_l=0
  • Si k\geq m+1, entonces a_k=0 y por lo tanto a_kb_l=0
  • Finalmente, si k=m, entonces l=n y

        \[a_kb_l=a_mb_n\neq 0.\]

De esta forma, el (m+n)-ésimo término de ab es

    \[\sum_{k+l=m+n} a_k b_l=a_mb_n\neq 0,\]

de modo que ab no es el polinomio (\overline{0}).

\square

Corolario. En \mathbb{R}[x] se vale la regla de cancelación, es decir, si a,b,c son polinomios, a\neq 0 y ab=ac, entonces b=c.

Demostración. De la igualdad ab=ac obtenemos la igualdad a(b-c)=0. Como a\neq 0, por la proposición anterior debemos tener b-c=0, es decir, b=c.

\square

A un anillo conmutativo cuya multiplicación tiene identidad y en donde se vale la regla de cancelación se le conoce como un dominio entero.

Teorema. El anillo \mathbb{R}[x] es un dominio entero.

Con esto terminamos la construcción de \mathbb{R}[x] y de sus operaciones. Cuando trabajamos con los polinomios de manera práctica resulta engorroso mantener esta notación de sucesiones. En la siguiente entrada justificaremos el uso de la notación «usual» de los polinomios, en la que usamos la letra «x» y exponentes.

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.

  • Justifica por qué el soporte del producto de dos polinomios es finito.
  • Muestra que la suma en \mathbb{R}[x] es asociativa.
  • Verifica que el polinomio (\overline{0}) es la identidad aditiva en \mathbb{R}[x].
  • Verifica que el polinomio (1,\overline{0}) es la identidad multiplicativa en \mathbb{R}[x].
  • Considera los polinomios a=\left(\frac{1}{3},4,\frac{5}{7},8,\overline{0}\right) y b=\left(0,0,\frac{2}{5},\frac{3}{4},\overline{0}). Determina

Seminario de Resolución de Problemas: Sucesiones recursivas y recursiones lineales

Introducción

En esta entrada estudiaremos aquellas sucesiones en las que un término está definido mediante términos anteriores. Estas son las sucesiones recursivas. Dentro de ellas hay unas muy especiales, que son las que satisfacen una recursión lineal. También hablaremos de eso.

En entradas anteriores ya hemos visto ejemplos de sucesiones recursivas. Por un lado, las sucesiones aritméticas y geométricas cumplen una recursión sencilla. Las sucesiones periódicas también se pueden poner en términos de una recursión.

Vimos otros ejemplos en la entrada de sucesiones monótonas y acotadas, en donde la recursion nos ayuda a demostrar algunas de estas propiedades.

Sucesiones recursivas

Una sucesión recursiva es una sucesión \{x_n\} en la que, intuitivamente, cada término depende de los anteriores. La regla que dice cómo está relacionado cada término con los de antes le llamamos la regla o fórmula recursiva. Usualmente los primeros términos de la sucesión están dados, y se les conoce como los términos iniciales.

Las sucesiones aritméticas son recursivas. Si \{x_n\} es aritmética de término inicial a y diferencia d, se comienza con x_0=a y para n\geq 0 se satisface la recursión x_{n+1}=x_n+d. Similarmente, una sucesión geométrica \{y_n\} de término inicial s y razón r se puede poner en términos recursivos: y_0=s y para n\geq 0, se tiene y_{n+1}=ry_n.

Una sucesión periódica \{z_n\} de periodo p también satisface una recursión. Los términos iniciales z_0,\ldots,z_{p-1} están dados y para n\geq 0 se tiene que z_{n+p}=z_n.

Las sucesiones recursivas pueden aparecer como parte del enunciado de un problema, o bien pueden aparecer de manera natural como parte de la solución de un problema.

Problema. Para un triángulo T del plano se define otro triángulo f(T) como sigue:

  • Se nombran los vértices A,B,C de modo que |BC|\leq |AC|\leq |AB|.
  • Al punto medio de BC se le nombra M.
  • Se rota el punto A alrededor de M en 180^\circ para obtener un punto A'.
  • Se define f(T) como el triángulo ACA'.

Definimos una sucesión de triángulos como sigue. Se toma T_0=T. Luego, para n\geq 0 se define T_{n+1}=f(T_n). ¿Es posible que esta sucesión tenga dos triángulos congruentes?

Sugerencia pre-solución. Es difícil estudiar las ternas de lados bajo la operación. Modifica el problema a entender otro parámetro que puedas estudiar fácilmente bajo las reglas dadas.

Solución. La respuesta es que en la sucesión no hay dos triángulos congruentes. De hecho, la observación clave es mostrar algo más fuerte: en la sucesión no hay dos triángulos con el mismo perímetro.

Tomemos un triángulo T. En el primer paso se nombran los vértices ABC de modo que BC el lado más chico del triángulo, y por lo tanto el ángulo en A es menor estrictamente a 90^\circ. Por esta razón, A está fuera del círculo con diámetro BC, y por lo tanto la mediana AM tiene longitud mayor a \frac{|BC|}{2}. El nuevo triángulo tiene lados de longitudes |AB|, |AC| y 2|AM|>|BC|.

Así, la sucesión de perímetros de los triángulos es estrictamente creciente. Por lo tanto, en la sucesión no puede haber dos triángulos con el mismo perímetro, y entonces no hay dos congruentes.

\square

Sucesiones recursivas y conteo

Las sucesiones recursivas aparecen también en problemas de combinatoria o de algoritmos, en donde ciertos casos o cierta cantidad de pasos se puede poner en términos de versiones más pequeñas del problema. Además, es posible que en un problema interactúen dos o más sucesiones de manera recursiva. Veamos un ejemplo.

Problema. Se tienen palabras de 10 letras que usan los símbolos a, b y c. ¿Cuántas de ellas no tienen dos a consecutivas, ni dos b consecutivas?

Sugerencia pre-solución. En vez de resolver el problema directamente, generalízalo a cuando se tienen palabras de n letras. Para contar cuántas son, divide en casos de acuerdo a en qué símbolo terminan y plantea una recursión en términos de valores anteriores. Hay cierta simetría en a y b. Aprovéchala.

Solución. Vamos a resolver un problema más general. Contemos las sucesiones sin dos a ni dos b consecutivas. Dividamos en los siguientes casos:

  • \{x_n\} será la sucesión que cuenta cuántas de n letras hay que terminen en a.
  • \{y_n\} será la sucesión que cuenta cuántas de n letras hay que terminen en b.
  • \{z_n\} será la sucesión que cuenta cuántas de n letras hay que terminen en c.

Por ejemplo, x_1=y_1=z_1=1, pues con una letra y con la letra final definida sólo hay una opción. Tenemos que x_2=2, que son

    \[ba,ca,\]

que y_2=2, que son

    \[ab,cb,\]

y que z_3=3, que son

    \[ac,bc,cc.\]

El problema nos pregunta por x_{10}+y_{10}+z_{10}.

La razón para partir en estos casos es que si sabemos en qué letra termina una sucesión, entonces sabemos exactamente cómo encontrar las que tienen una letra más de manera recursiva. Por ejemplo, para n\geq 1 tenemos que x_{n+1}=y_n+z_n, pues una palabra buena de n+1 letras que termina en a se forma por una palabra buena de n letras que no termina en a, y luego al final se le pone una a. Las tres recursiones que obtenemos son

    \begin{align*}x_{n+1}&=y_n+z_n\\y_{n+1}&=x_n+z_n\\z_{n+1}&=x_n+y_n+z_n.\end{align*}

Ahora sí podemos hacer las cuentas únicamente haciendo operaciones, sin la dificultad que implica llevar el conteo de casos en el problema original. La siguiente tabla se puede llenar fácilmente, llenando renglón a renglón de arriba a abajo. Además, la simetría del problema en a y b hace que las sucesiones x_n y y_n sean iguales, así que también podemos aprovechar esto al momento de hacer las cuentas:

nx_ny_nz_n
1111
2223
3559
4141419
5333347
68080113
7193193273
8466466659
9112511251591
10271627163841
Tabla de valores de las sucesiones

De esta manera, la cantidad total de palabras que pide el problema es

    \[2716+2716+3841=9273.\]

\square

Recursiones lineales

Hay un tipo de sucesiones recursivas especiales, que cumplen que cada término depende de pocos términos anteriores y de manera lineal.

Por ejemplo, la sucesión de Fibonacci satisface F_0=0, F_1=1 y para k\geq 0 se tiene que

    \[F_{k+2}=F_k+F_{k+1}.\]

Aquí la recursión depende de los dos términos inmediatos anteriores, y cada uno de ellos aparece linealmente. Por ello, decimos que es una recursión lineal de orden 2.

La definición general es la siguiente.

Definición. Una sucesión \{x_n\} de reales satisface una recursión lineal de orden m si los primeros m términos x_0,\ldots,x_{m-1} están dados, y además existen reales a_0,\ldots,a_{m-1} tales que para k\geq 0 se satisface la recursión lineal

    \[x_{m+k}=a_0x_k+a_1x_{k+1}+\ldots+a_{m-1}x_{m+k-1}.\]

El siguiente método nos ayuda en varios casos a pasar una sucesión que satisface una recursión lineal a una fórmula cerrada.

Primero, tomamos una sucesión \{x_n\} como la de la definición. Luego, consideramos el siguiente polinomio de grado m:

    \[P(x)=x^m-a_{m-1}x^{m-1}-\ldots-a_0.\]

Supongamos que r es una raíz de P. Afirmamos que la sucesión \{r^n\} satisface la recursión. En efecto, como r es raíz de P, tenemos que

    \[r^m=a_{m-1}r^{m-1}+\ldots+a_0,\]

y multiplicando ambos lados por r^k tenemos que

    \[r^{m+k}=a_{m-1}r^{m+k-1}+\ldots+a_0r^k,\]

que es justo la recursión lineal (con los sumandos de derecha a izquierda).

Ahora, nota que si \{x_n\} y \{y_n\} satisfacen la recursión lineal, entonces para cualesquiera reales c y d tenemos que \{cx_n+dy_n\} también. Entonces si hacemos combinaciones lineales de potencias de raíces de P también tendremos sucesiones que satisfacen la recursión lineal. Resulta que en varios casos «todas las soluciones se ven así».

La discusión hasta aquí es un poco abstracta, así que hagamos un ejemplo concreto.

Problema. Determina una fórmula cerrada para la sucesión \{A_n\} tal que A_0=1, A_1=5 y que satisface la recursión lineal de orden 2

    \[A_{n+2}=-6A_n+5A_{n+1}.\]

Sugerencia pre-solución. Encuentra el polinomio asociado a la recursión. Si tiene raíces \alpha y \beta, muestra que para cualesquiera reales c y d se tiene que B(c,d)=\{c\alpha^n+d\beta^n\} satisface la recursión. Ya que nos dan los dos primeros términos, se puede encontrar los únicos c y d que funcionan para \{A_n\}.

Solución. El polinomio asociado a la recursión es x^2-5x+6, que tiene raíces 2\,\text{ y }\, 3. Entonces, para cualesquiera reales c y d se tiene que la sucesión B(c,d)=\{c2^n+d3^n\} satisface la recursión.

Además, necesitamos que los primeros términos sean 1\,\text{ y }\,5 respectivamente, de donde obtenemos el sistema de ecuaciones para c y d siguiente:

    \begin{align*}1&=c2^0+d3^0=c+d\\5&=c2^1+d3^1=2c+3d.\end{align*}

La solución a este sistema es c=-2, d=3. De esta forma, la fórmula cerrada para \{A_n\} es

    \[A_n=-2\cdot 2^n+3\cdot 3^n=3^{n+1}-2^{n+1}.\]

\square

Todos los pasos que hicimos en el problema anterior son reversibles, pero si quieres asegurarte de que todo va marchando bien, puedes mostrar por inducción que la fórmula dada es correcta.

Teorema para recursiones lineales de orden m

Resulta que cuando el polinomio asociado tiene m raíces distintas, entonces el método anterior siempre funciona.

Teorema. Supongamos que la sucesión \{x_n\} satisface la recursión lineal de orden m

    \[x_{m+k}=a_0x_k+a_1x_{k+1}+\ldots+a_{m-1}x_{m+k-1}\]

para ciertos reales a_0,\ldots,a_{m-1}, y que las raíces del polinomio

    \[P(x)=x^m-a_{m-1}x^{m-1}-\ldots-a_0\]

son todas distintas y son r_0,\ldots,r_{m-1}. Entonces, existen únicos números c_0,\ldots,c_{m-1} tales que para todo n\geq 0 se tiene

    \[x_n=c_0r_0^n+\ldots+c_{m-1}r_{m-1}^n,\]

y ellos se pueden encontrar mediante el sistema de m ecuaciones lineales que queda al tomar n=0,1,\ldots,m-1.

No veremos la demostración de este teorema, pero aquí abajo lo usaremos para resolver algunos problemas.

Problema. La sucesión \{B_n\} satisface que para toda n\geq 0 se tiene que

    \[B_{n+5}+B_n=-2(B_{n+4}+B_{n+1})-3(B_{n+3}+B_{n+2}).\]

Demuestra que esta sucesión es acotada.

Sugerencia pre-solución. Calcula el polinomio asociado. Factorízalo y muestra que todas sus raíces son diferentes.

Solución. Reacomodando los términos en la hipótesis, obtenemos que \{B_n\} satisface una recursión lineal con polinomio asociado

    \[P(x)=x^5+2x^4+3x^3+3x^2+2x+1,\]

que se puede factorizar como

    \[(x^2+x+1)(x^3+x^2+x+1).\]

Las raíces del primer factor son las dos raíces cúbicas de la unidad que no sean uno digamos w y z. Las del segundo factor son las 3 raíces cuartas de la unidad que no sean uno, es decir i, -1 y -i.

Todos estos complejos tienen norma uno y además son distintos. De esta forma, por el teorema de recursiones lineales, existen únicos complejos a,b,c,d,e tales que para toda n se cumple

    \[B_n=aw^n+bz^n+ci^n+d(-1)^n+e(-i)^n.\]

De aquí podemos proceder de dos formas distintas. Una es simplemente tomando norma de ambos lados y usando la desigualdad del triángulo:

    \begin{align*}|B_n|&=\norm{aw^n+bz^n+ci^n+d(-1)^n+e(-i)^n}\\&\leq \norm{aw^n}+\norm{bz^n}+\norm{ci^n}+\norm{d(-1)^n}+\norm{e(-i)^n}\\&= \norm{a}+\norm{b}+\norm{c}+\norm{d}+\norm{e},\end{align*}

lo cual muestra que B_n está acotada.

La otra es usar que para cada raíz m-ésima de la unidad \alpha y cualquier constante r se tiene que \{r\alpha^n\} es periódica de periodo m. De esta forma, \{B_n\} es suma de sucesiones periódicas, y por lo tanto es periódica. Como es periódica, entonces es acotada.

\square

Existe una forma sistemática para lidiar con recursiones lineales cuando las raíces del polinomio anterior no son diferentes. Sin embargo, ella requiere de un buen entendimiento de matrices y diagonalización, que es un tema no trivial en álgebra lineal. De cualquier forma, el método anterior funciona en una gran variedad de situaciones.

Recursiones lineales y sumas de potencias

Quizás lo más importante del método anterior es que da la siguiente intuición:

«Las sucesiones \{x_n\} que satisfacen una recursión lineal de orden m y las expresiones del estilo

    \[S_n=c_0r_0^n+\ldots+c_{m-1}r_{m-1}^n\]

están fuertemente relacionadas.»

Así, cuando se tiene una combinación lineal de potencias n-ésimas, una de las primeras cosas que hay que hacer es ver si la recursión lineal que satisface nos ayuda para el problema. El siguiente problema es el Problema 1 de la primer Competencia Iberoamericana Interuniversitaria de Matemáticas

Problema. Muestra que para todo entero positivo n se tiene que la expresión \left(\frac{3+\sqrt{17}}{2}\right)^n+\left(\frac{3-\sqrt{17}}{2}\right)^n es un entero impar.

Sugerencia pre-solución. Ya discutimos cómo pasar de una recursión lineal a una suma de potencias. Ahora tienes que trabajar al revés para encontrar una recursión lineal que satisfaga la expresión del problema.

Solución. Sean \alpha=\frac{3+\sqrt{17}}{2} y \beta=\frac{3-\sqrt{17}}{2}. El problema pide mostrar que para n entero positivo se tiene que x_n:=\alpha^n+\beta^n es un entero impar.

Como \alpha y \beta son raíces del polinomio

    \begin{align*}P(x)&=(x-\alpha)(x-\beta)\\&=x^2-(\alpha+\beta)x+\alpha\beta\\&=x^2-3x-2,\end{align*}

se tiene que x_n satisface la recursión lineal de orden dos siguiente:

    \[x_{n+2}=3x_{n+1}+2x_n.\]

Con esto, estamos listos para mostrar inductivamente que x_n es impar para todo entero positivo n. Se tiene que x_0=2 y x_1=\alpha+\beta=3, de modo que por la recursión, x_2=13, así que la afirmación es cierta para n=1,2.

Si la afirmación es cierta hasta un entero positivo n-1, usamos la recursión para mostrar que x_n=3x_{n-1}+2x_{n-2} es la suma de un entero impar y un entero par, de modo que x_n es impar. Esto termina la demostración.

\square

Más problemas

Esta entrada es una extensión de la sección 7 del curso de sucesiones que impartí para los entrenadores de la Olimpiada Mexicana de Matemáticas. Puedes consultar las notas de este curso en el siguiente PDF, en donde hay más problemas de práctica:

Seminario de Resolución de Problemas: Sucesiones monótonas y acotadas

Introducción

En entradas anteriores hablamos de sucesiones aritméticas y geométricas. También hablamos de sucesiones periódicas y pre-periódicas. Cuando una sucesión es de cualquiera de estos tipos, entonces no es tan compleja pues depende de pocos parámetros. Hay otros dos sentidos en los que podemos restringir una sucesión: orden y en tamaño. Esto nos da, respectivamente, las definiciones de sucesiones monótonas y acotadas.

Por un lado, para hablar de sucesiones acotadas se necesita una noción de distancia. Por otro, para hablar de sucesiones monótonas se necesita de una noción de orden. En las siguientes secciones veremos ejemplos numéricos, pero mucho de lo que discutimos en esta entrada es generalizable a espacios métricos o conjuntos ordenados arbitrarios.

A menos que digamos lo contrario, supondremos que las sucesiones de las que hablamos empiezan con un término de subíndice 0, aunque esto en realidad no afecta las ideas que discutimos.

Sucesiones acotadas

Las sucesiones acotadas son aquellas que siempre están «cerca de un punto». Cuando estamos hablando de sucesiones de reales, o de elementos en un conjunto linealmente ordenado, podemos hablar de cotas por arriba y por abajo.

Definición. Sea \{x_n\} una sucesión de reales. Decimos que \{x_n\} es:

  • Inferiormente acotada si existe un real m tal que x_n\geq m para todo entero n\geq 0.
  • Superiormente acotada si existe un real M tal que x_n\leq M para todo entero n\geq 0.
  • Acotada si es inferiormente acotada y superiormente acotada.

Se puede usar como definición alternativa del tercer punto la conclusión de siguiente proposición. Esto permite definir sucesiones acotadas en cualquier espacio normado.

Proposición. Sea \{x_n\} una sucesión de reales. Se tiene que \{x_n\} es acotada si y sólo si existe un real A\geq 0 tal que |x_n|\leq A para todo entero n\geq 0.

Cualquier sucesión periódica de reales toma sólo una cantidad finita de valores, así que es acotada. ¿Cómo son las sucesiones aritméticas y geométricas que son acotadas?

Problema. La sucesión \{x_n\} está definida para n\geq 1 y está dada por

    \[x_n=3+\sqrt{3+\sqrt{3+\sqrt{\ldots\sqrt{3+\sqrt{3}}}}},\]

en donde tenemos n signos de raíz cuadrada. Muestra que esta sucesión es acotada.

Sugerencia pre-solución. La notación es algo difícil. Usa una mejor notación, conjetura una cota superior trabajando hacia atrás, y pruébala por inducción.

Solución. El primer término es 3+\sqrt{3} y para n\geq 1 tenemos

    \[x_{n+1}=3+\sqrt{x_n} \geq 0.\]

Falta ver que la sucesión está acotada superiormente.

Trabajemos hacia atrás, suponiendo que podemos mostrar por inducción que un real C es cota superior. Al hacer el paso inductivo, nos bastaría que

    \[3+\sqrt{C}\leq C.\]

Esto se cumple para muchos valores de C, por ejemplo, podemos tomar C=9.

Hagamos la prueba formalmente. Mostraremos que \{x_n\} está acotada superiormente por 9. El primer término es 3+\sqrt{3}, que está acotado por 9. Si x_n está acotado por 9, entonces

    \[x_{n+1}=3+\sqrt{x_n}\leq 3+\sqrt{9}\leq 3+3 \leq 9.\]

Esto termina la inducción y muestra que \{x_n\} es acotada.

\square

Sucesiones monótonas

Otra forma de limitar los «movimientos» de una sucesión es a través de una noción de orden. Las siguientes definiciones son para sucesiones de reales, pero es sencillo extenderlas a cualquier conjunto parcialmente ordenado.

Definición. Sea \{x_n\} una sucesión de reales. Decimos que \{x_n\} es:

  • Creciente si para todo par de enteros enteros k>l\geq 0 se tiene que x_k\geq x_l.
  • Estrictamente creciente si para todo par de enteros enteros k>l\geq 0 se tiene que x_k> x_l.
  • Decreciente si para todo par de enteros enteros k>l\geq 0 se tiene que x_k\leq x_l.
  • Estrictamente decreciente si para todo par de enteros enteros k>l\geq 0 se tiene que x_k<x_l.

Las sucesiones monótonas son aquellas que cumplen alguna de las definiciones anteriores.

Aunque la definición requiere que cierta desigualdad se cumpla para todo par de índices k>l\geq 0, basta con demostrar que se cumple para k=n+1 y l=n, es decir, para índices consecutivos. Esto típicamente se reduce a demostrar una desigualdad. Hablaremos más adelante de técnicas para resolver desigualdades, pero por el momento veremos un ejemplo sencillo.

Problema. Muestra que la sucesión \{x_n\} dada por

    \[x_n=\left(1 +\frac{1}{n}\right)^n\]

es estrictamente creciente.

Sugerencia pre-solución. Basta con que pruebes la desigualdad para subíndices consecutivos. Para hacer esto, usa el binomio de Newton y modifica el problema a comparar ciertos términos.

Solución. Tenemos que mostrar que

    \[\left(1+\frac{1}{n}\right)^{n} \leq \left(1+\frac{1}{n+1}\right)^{n+1}.\]

Para mostrar esto, primero demostraremos la siguiente desigualdad auxiliar para 0\leq k \leq n+1:

(1)   \begin{equation*}\binom{n}{k}\frac{1}{n^k}\leq \binom{n+1}{k}\frac{1}{(n+1)^k}.\end{equation*}

Si k=n+1, la desigualdad se cumple pues el término izquierdo es 0. Para 0\leq k \leq n, esta desigualdad es equivalente a la desigualdad

    \[\frac{\binom{n+1}{k}}{\binom{n}{k}}\geq \left(\frac{n+1}{n}\right)^k.\]

Usando la expresión en términos de factoriales y simplificando el lado izquierdo, tenemos que

    \begin{align*}\frac{\binom{n+1}{k}}{\binom{n}{k}}&=\frac{\frac{(n+1)!}{k!(n+1-k)!}}{\frac{n!}{k!(n-k)!}}\\&=\left(\frac{n+1}{n}\right)\cdot\left(\frac{n}{n-1}\right)\cdot \ldots\cdot\left(\frac{n+2-k}{n+1-k}\right)\end{align*}

Afirmamos que cada uno de los k términos de la derecha es mayor o igual a \frac{n+1}{n}. Para ello, basta mostrar que la sucesión \left\{\frac{m+1}{m}\right\} definida para m\geq 1 es decreciente. Pero esto es fácil de ver, pues cada término es \frac{m+1}{m}=1+\frac{1}{m} que claramente decrece conforme m crece. Con esto terminamos la prueba de la desigualdad auxiliar (1).

Sumando la desigualdad (1) para todos los valores de k de 0 a n+1 y usando el binomio de Newton, obtenemos la desigualdad deseada.

\square

Más allá de sucesiones monótonas

De entre las sucesiones monótonas, hay algunas que podemos entender mejor. Una sucesión de reales puede ser estrictamente creciente, y no irse a infinito. Por ejemplo, considera la sucesión:

    \[0.3, 0.33, 0.333, 0.3333,\ldots\]

en donde de un término al siguiente se agrega un dígito 3. Esta sucesión es estrictamente creciente, pero todos los términos son menores a \frac{1}{3}.

Hay diferentes grados de información que podemos tener de una sucesión con respecto a cuánto crece. En cada uno de los siguientes puntos, cada vez sabemos mejor qué tanto crece la sucesión:

  • Saber que la sucesión es creciente
  • Saber que es estrictamente creciente
  • Determinar si es acotada superiormente
  • Conocer qué tan rápido crece

Por supuesto, hay una jerarquía análoga para funciones decrecientes.

Veamos un ejemplo de entender bien el crecimiento de una sucesión. El siguiente problema apareció en uno de los concursos de matemáticas Pierre Fermat que organiza el IPN.

Problema. Considera una sucesión \{a_n\} de reales tal que a_0>0 y para cada n\geq 0 se cumple que a_{n+1}=a_n+\frac{1}{a_n}. Muestra que a_{200}>20.

Sugerencia pre-solución. En vez de entender la sucesión \{a_n\}, modifica el problema a entender la sucesión \{a_n^2\}, que es más fácil de estudiar cómo crece. En cierta forma, tendrás que generalizar el problema, entendiendo qué tan grande es cada término.

Solución. Es fácil ver que la sucesión es creciente. Para ello podemos probar simultáneamente por inducción que cada término es positivo y mayor que el anterior. Sin embargo, esto es todavía muy débil para nuestros fines: aún no sabemos si la sucesión superará 20 y, peor aún, no sabemos si sucederá antes del término 200.

Quedémonos con el hecho de que a_n es de términos positivos. Pero en vez de estudiar cómo crece \{a_n\}, mejor estudiamos cómo crece \{a_n^2\}. Observemos que

    \begin{align*}a_{n+1}^2&=\left(a_n+\frac{1}{a_n}\right)^2\\&=a_n^2+2+\frac{1}{a_n^2}\\&>a_n^2+2,\end{align*}

de modo que podemos probar inductivamente que a_n^2\geq 2n. De aquí, deducimos que a_n\geq \sqrt{2n}. En particular, a_{200}\geq \sqrt{400}=20.

\square

Descenso infinito

Una herramienta bastante útil para la resolución de problemas con enteros es el siguiente resultado. En cierto sentido, habla de cómo son las sucesiones monótonas y acotadas de enteros.

Teorema (principio del descenso infinito). No existen sucesiones estrictamente decrecientes e inferiormente acotadas de enteros.

De manera similar, no existen sucesiones estrictamente crecientes y superiormente acotadas de enteros.

Veamos un ejemplo de la Olimpiada Centroamericana de Matemáticas.

Problema. Aplicar un desliz a un entero positivo n\geq 5 consiste en cambiar a n por \frac{n+p^2}{p}, con p un divisor primo de n. Muestra que tras aplicar repetidamente deslices a un entero n\geq 5, siempre se llega a 5.

Sugerencia pre-solución. Usa el principio de descenso infinito.

Solución. Si comenzamos con n=5, la única opción es pasar a \frac{5+25}{5}=6. Si comenzamos con n=6, ambos deslices (con 2 ó 3) nos llevan a 5.

Veremos que a partir de cualquier entero n\geq 7, tras aplicar deslices siempre se llega a 5.

Afirmamos lo siguiente:

  • Si n es primo, sólo tiene un desliz que lo pasa a n+1.
  • Para n\geq 7 no primo, aplicar un desliz lo disminuye en al menos 2.
  • Para n\geq 5, aplicar un desliz lo lleva a un número mayor o igual a 5.

La primera afirmación es fácil de ver, pues si n=p, el único divisor primo que tiene es p y así, el único desliz que tiene lo manda a

    \[\frac{p^2+p}{p}=p+1=n+1.\]

Para la segunda afirmación, necesitamos mostrar que si n\geq 7 no es primo y p lo divide, entonces

    \[\frac{n+p^2}{p}\leq n-2.\]

Reescribiendo esta afirmación, necesitamos mostrar que

    \[np\geq p^2+n+2p.\]

Como n no es primo, n=pq con q\geq 2. Como p es primo, p\geq 2.

Reescribiendo la desigualdad que queremos mostrar en términos de p y q, y cancelando un factor p de ambos lados, lo que necesitamos es

    \[pq\geq p+q+2.\]

restando p+q-1 de ambos lados y factorizando el lado izquierdo, esto es equivalente a

    \[(p-1)(q-1)\geq 3.\]

Hagamos un análisis de casos para los primos p y q

  • Si p=q=2 entonces n=4, que no es un caso que nos interese.
  • Si p=2 y q=3, o p=3 y q=2, entonces n=6, pero para la segunda afirmación estamos suponiendo n\geq 7.
  • Así, p\geq 3 y q\geq 3, de modo que (p-1)(q-1)\geq 4, que implica la desigualdad que queremos.

Esto prueba la segunda afirmación.

La tercera afirmación se prueba notando que tras el desliz, un número se va a \frac{n}{p}+p \geq  2\sqrt{n}\geq 2\sqrt{5}>4, y como esta esta expresión es entera, se tiene \frac{n}{p}+p\geq 5.

Estamos listos para dar la prueba. Por la tercer afirmación, la sucesión siempre es \geq 5. Si acaso la sucesión crece, fue porque teníamos un primo p que pasó a p+1. Pero entonces p+1 no es primo y al paso siguiente es menor o igual a p-1 por la segunda afirmación. Así, cada dos pasos, la sucesión decrece estrictamente, a menos que pase por 6. Por el principio de descenso infinito, no es posible que siempre decrezca. Así, en algún momento pasa por 6, y entonces al paso siguiente será 5.

\square

Más problemas

Esta entrada es una extensión de las secciones 1, 2 y 3 del curso de sucesiones que impartí para los entrenadores de la Olimpiada Mexicana de Matemáticas. Puedes consultar las notas de este curso en el siguiente PDF, en donde hay más problemas de práctica: