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 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 es aritmética de término inicial
y diferencia
, se comienza con
y para
se satisface la recursión
. Similarmente, una sucesión geométrica
de término inicial
y razón
se puede poner en términos recursivos:
y para
, se tiene
.
Una sucesión periódica de periodo
también satisface una recursión. Los términos iniciales
están dados y para
se tiene que
.
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 del plano se define otro triángulo
como sigue:
- Se nombran los vértices
de modo que
.
- Al punto medio de
se le nombra
.
- Se rota el punto
alrededor de
en
para obtener un punto
.
- Se define
como el triángulo
.
Definimos una sucesión de triángulos como sigue. Se toma . Luego, para
se define
. ¿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 . En el primer paso se nombran los vértices
de modo que
el lado más chico del triángulo, y por lo tanto el ángulo en
es menor estrictamente a
. Por esta razón,
está fuera del círculo con diámetro
, y por lo tanto la mediana
tiene longitud mayor a
. El nuevo triángulo tiene lados de longitudes
,
y
.
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.
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 letras que usan los símbolos
,
y
. ¿Cuántas de ellas no tienen dos
consecutivas, ni dos
consecutivas?
Sugerencia pre-solución. En vez de resolver el problema directamente, generalízalo a cuando se tienen palabras de 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
y
. Aprovéchala.
Solución. Vamos a resolver un problema más general. Contemos las sucesiones sin dos ni dos
consecutivas. Dividamos en los siguientes casos:
será la sucesión que cuenta cuántas de
letras hay que terminen en
.
será la sucesión que cuenta cuántas de
letras hay que terminen en
.
será la sucesión que cuenta cuántas de
letras hay que terminen en
.
Por ejemplo, , pues con una letra y con la letra final definida sólo hay una opción. Tenemos que
, que son



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 tenemos que
, pues una palabra buena de
letras que termina en
se forma por una palabra buena de
letras que no termina en
, y luego al final se le pone una
. Las tres recursiones que obtenemos son
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 y
hace que las sucesiones
y
sean iguales, así que también podemos aprovechar esto al momento de hacer las cuentas:
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() |
De esta manera, la cantidad total de palabras que pide el problema es
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 ,
y para
se tiene que
La definición general es la siguiente.
Definición. Una sucesión de reales satisface una recursión lineal de orden
si los primeros
términos
están dados, y además existen reales
tales que para
se satisface la recursión lineal
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 como la de la definición. Luego, consideramos el siguiente polinomio de grado
:
Supongamos que es una raíz de
. Afirmamos que la sucesión
satisface la recursión. En efecto, como
es raíz de
, tenemos que

Ahora, nota que si y
satisfacen la recursión lineal, entonces para cualesquiera reales
y
tenemos que
también. Entonces si hacemos combinaciones lineales de potencias de raíces de
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 tal que
,
y que satisface la recursión lineal de orden 2
Sugerencia pre-solución. Encuentra el polinomio asociado a la recursión. Si tiene raíces y
, muestra que para cualesquiera reales
y
se tiene que
satisface la recursión. Ya que nos dan los dos primeros términos, se puede encontrar los únicos
y
que funcionan para
.
Solución. El polinomio asociado a la recursión es , que tiene raíces
. Entonces, para cualesquiera reales
y
se tiene que la sucesión
satisface la recursión.
Además, necesitamos que los primeros términos sean respectivamente, de donde obtenemos el sistema de ecuaciones para
y
siguiente:
La solución a este sistema es ,
. De esta forma, la fórmula cerrada para
es
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 
Resulta que cuando el polinomio asociado tiene raíces distintas, entonces el método anterior siempre funciona.
Teorema. Supongamos que la sucesión satisface la recursión lineal de orden






No veremos la demostración de este teorema, pero aquí abajo lo usaremos para resolver algunos problemas.
Problema. La sucesión satisface que para toda
se tiene que
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 satisface una recursión lineal con polinomio asociado
Las raíces del primer factor son las dos raíces cúbicas de la unidad que no sean uno digamos y
. Las del segundo factor son las
raíces cuartas de la unidad que no sean uno, es decir
,
y
.
Todos estos complejos tienen norma uno y además son distintos. De esta forma, por el teorema de recursiones lineales, existen únicos complejos tales que para toda
se cumple
De aquí podemos proceder de dos formas distintas. Una es simplemente tomando norma de ambos lados y usando la desigualdad del triángulo:
lo cual muestra que está acotada.
La otra es usar que para cada raíz -ésima de la unidad
y cualquier constante
se tiene que
es periódica de periodo
. De esta forma,
es suma de sucesiones periódicas, y por lo tanto es periódica. Como es periódica, entonces es acotada.
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
que satisfacen una recursión lineal de orden
y las expresiones del estilo
están fuertemente relacionadas.»
Así, cuando se tiene una combinación lineal de potencias -é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 se tiene que la expresió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 y
. El problema pide mostrar que para
entero positivo se tiene que
es un entero impar.
Como y
son raíces del polinomio
se tiene que satisface la recursión lineal de orden dos siguiente:
Con esto, estamos listos para mostrar inductivamente que es impar para todo entero positivo
. Se tiene que
y
, de modo que por la recursión,
, así que la afirmación es cierta para
.
Si la afirmación es cierta hasta un entero positivo , usamos la recursión para mostrar que
es la suma de un entero impar y un entero par, de modo que
es impar. Esto termina la demostración.
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: