Libro Ecuaciones De Recurrencia

6. ECUACIONES DE RECURRENCIA.

6.1. Introducción.
Las relaciones de recurrencia pueden considerarse como técnicas avanzadas de
conteo. Resuelven problemas cuya solución no puede obtenerse usando variaciones,
permutaciones, combinaciones o con las técnicas derivadas del principio de
inclusión-exclusión.
Recordemos que una sucesión es una función f: A. Para indicar la imagen en
el conjuntoA de n, esto es f(n), se emplea el símbolo an.
£ ¡ ¡¡¡ ¢ 
¡

Una sucesión suele denotarse por a0,a1,a2,a3,..., por {an:n∈ }, por {an}n∈ o
por {an}. A los elementos a0,a1,a2... se les llama términos de la sucesión, de an
se dice que es el término general.
Para introducir la teoría de las relaciones de recurrencia, tomemos como
 

 

ejemplo la conocida sucesión de Fibonacci1,1,2,3,5,8,13,... donde cada término, a
partir del tercero, se obtiene sumando los dos anteriores, esto es:
an=an-1+an-2
si n≥3,
Una expresión de este tipo, en la que el término general de la sucesión se
escribe en función de algunos otros términos anteriores, recibe los nombres de
relación de recurrencia, ecuación de recurrencia o ecuación en diferencias.
La relación de recurrencia no determina demanera única la sucesión. Para
ello es necesario conocer algunos términos de la sucesión, lo que llamaremos
condiciones iniciales o condiciones frontera. En el caso anterior a1=1 y a2=1.
Ejemplo: Las sucesiones
1,2,4,8,16,...
3,6,12,24,48,...
satisfacen la misma relación de recurrencia an=2an-1, si n≥1. La condición inicial
a0=1 junto con esta relación de recurrencia determinan de forma únicala primera.
El conjunto {an=2an-1 si n≥1, a0=3} define la segunda.
Si queremos obtener un término concreto de una sucesión dada en forma
recurrente debemos ir obteniendo todos los anteriores lo cual no parece muy
práctico, (¿cual es el valor a100 en la sucesión de Fibonacci?). Interesa pues,
determinar una expresión del tipo an=g(n) en la que el término general de la
133

sucesióndependa sólo de la posición que ocupa y no de términos anteriores. A una
expresión de este tipo se llama solución de la ecuación de recurrencia.
Ejemplo 1. Para las siguientes ecuaciones de recurrencia la solución se obtiene de
forma elemental.
1.1) Para an=3an-1 si n≥1, a0=5 se tiene
a0= 5,
a1= 3a0= 3x5,
a2= 3a1= 32x5,
y aplicando inducción se obtiene que la sucesión solución es
an= 3nx5
1.2)Sea an-an-1=(n-1) si n≥1 con a1=0. Despejando an=an-1+(n-1) se tiene
a1= 0,
a2= a1+1= 0+1,
a3= a2+2= 0+1+2,
...
an= 0+1+2+...+(n-1) =(n-1)n/2
1.3) an-nan-1=0 si n≥1, a0=1
a0= 1,
a1= 1.a0= 1,
a2= 2.a1= 2x1,
a3= 3.a2= 3x2x1,
...
an= nx(n-1)x...x3x2x1= n!
No nos ocuparemos de ecuaciones como esta última en la que el coeficiente de
an-1 es variable. Trataremos sólamente de lasecuaciones de recurrencia lineales
con coeficientes constantes que definimos a continuación.
Definición. Una ecuación de recurrencia lineal de orden k con coeficientes
constantes es una relación
cnan+cn-1an-1+...+cn-kan-k= bn, n≥k
(I)
donde cn,cn-1,...,cn-k son constantes con cn≠0 y cn-k≠0 y {bn}n∈ es una sucesión
conocida. Diremos que (I) es homogénea si bn=0.
 

Centraremos nuestra atención enel cálculo explícito de la solución de tales
ecuaciones. El problema consiste en determinar la solución {an}n∈ en forma
 

134

cerrada, es decir expresar an como una función conocida de n. Si fijamos
condiciones iniciales, esto es valores para a0,a1,...,ak-1, la solución de (I)
está unívocamente determinada.
En general encontrar la solución de una ecuación de recurrencia no es fácil.Veamos cómo hacerlo para cierta familia de ecuaciones de recurrencia.

6.2. Ecuación de recurrencia lineal homogénea.
Antes de generalizar, comenzamos obteniendo la solución de la ecuación
homogénea de primer y segundo orden.
La ecuación de recurrencia homogénea de orden 1
an= c.an-1 n≥1, c≠0
verifica an= can-1= c2an-2= c3an-3= ...= cna0.
Por tanto la solución es de la forma an= α.cn con...