recurrencia

Ecuaciones de recurrencia
Introducción
Comencemos con un ejemplo:
Sucesión de Fibonacci: ( an ) = ( 1,1, 2,3,5,8,13,...)
Cada término, a partir del tercero, se obtiene sumando los dos anteriores, o sea:
an = an − 1 + an − 2 ( n ≥ 3)
Una expresión de este tipo, en que el término general de la sucesión se escribe en función de
algunos términos anteriores, recibe el nombre de relación derecurrencia, ecuación de
recurrencia o ecuación en diferencias.
Para obtener un término concreto de una sucesión dada en forma recurrente debemos ir
obteniendo todos los anteriores, lo cual no siempre es práctico. ¿Cuál es el término a100 de la
sucesión de Fibonacci?
Encontrar una solución a la ecuación de recurrencia es determinar una expresión del tipo
an = f (n ) en la que el término generaldependa solo de la posición que ocupa y no de los
anteriores.
Para que la solución sea única es necesario conocer algunos términos de la sucesión, lo que
llamaremos condiciones iniciales. En el ejemplo anterior a1 = 1 y a2 = 1 .

Ejemplo: Las sucesiones (1, 2, 4, 8, 16, ...) y (3, 6, 12, 24, 48, ...) satisfacen la misma relación
de recurrencia an = 2an − 1 , si n ≥ 1 . Pero la condicióninicial a0 = 1 junto con la relación de
recurrencia determinan de forma única la primera de estas dos sucesiones. La condición inicial
a0 = 3 junto con an = 2an − 1 para n ≥ 1 , determina la segunda.

Definición: Una ecuación de recurrencia lineal de orden k con coeficientes constantes es
una relación
cn an + cn − 1an − 1 + cn − 2 an − 2 + ... + cn − k an − k = bn , n ≥ k
(I)
donde cn , cn − 1,..., cn − k son constantes ( ≠ 0 ) y ( bn ) es una sucesión conocida. Diremos que (I) es
homogénea si bn = 0 .

Matemática II- INET
Profesora Patricia Echenique Viñas

-1-

Ecuación de recurrencia lineal homogénea
Ecuación de recurrencia lineal de primer orden
Sea ( an ) : an = 3an − 1 (esta expresión no define una única progresión geométrica, debemos dar las
condiciones iniciales)Sea entonces ( an ) : an = 3an − 1 , con n ≥ 1 y a0 = 5
Esta ecuación de recurrencia an = 3an − 1 depende del elemento inmediato anterior, por eso decimos
que es de primer orden.
a0 = 5
a1 = 3a0 = 3 ⋅ 5
a2 = 3a1 = 3 ⋅ ( 3a0 ) = 3 ⋅ 3 ⋅ 5 = 32 ⋅ 5
a3 = 3a2 = 3 ⋅ ( 3 ⋅ ( 3a0 ) ) = 33 ⋅ 5
.
.
.
an = 3n ⋅ 5 esta es la solución de la ec. de recurrencia
Ejercicio 1: Encuentra la solucióngeneral de las siguientes ecuaciones de recurrencia
a) bn = 6bn − 1 con n ≥ 1, b0 = 13
1
b) cn = cn − 1 con n ≥ 1, c0 = 7
5
En general:
La solución de la ecuación de recurrencia

an = d ⋅ an − 1

con n ≥ 1, a0 = A

es

an = A ⋅ d n
Ejemplo: Resolver an = 7 ⋅ an − 1 , n ≥ 1 y a2 = 98
an = 7 ⋅ a n − 1 ⇒ d = 7
an = A ⋅ d n
a2 = A ⋅ 7n ⇒ 98 = A ⋅ 7 2 ⇒ A = 2
Por lo que la solución es:an = 2 ⋅ 7 n

Matemática II- INET
Profesora Patricia Echenique Viñas

-2-

Ejercicio 2: Encuentra la solución general de:
n ≥ 0 a0 = 3
a) an + 1 = 1,5an
n ≥ 0 a1 = 4
b) 3an + 1 − 4an = 0
2
2
Ejercicio 3: Determina an si an + 1 = 5an

an > 0, n ≥ 0 y a0 = 2

( Sugerencia: cambio de variable bn = a )
2
n

Ejercicio 4: Un banco paga un interés (compuesto mensual) del 6%anual. Si se depositan U $
1000 el 1º de abril, ¿cuánto dinero tendrá 3 meses después?

Ecuación de recurrencia lineal de segundo orden
cn an + cn − 1an − 1 + cn − 2 an − 2 = 0

n ≥ 2 (homogénea)

Se busca una solución de la forma

a n = Ar n
Sustituyendo en : cn an + cn − 1an − 1 + cn − 2 an − 2 = 0
cn Ar n + cn − 1 Ar n − 1 + cn − 2 Ar n − 2 = 0

n− 2
2
Factorizando se obtiene: r ( cnr + cn − 1r + cn − 2 ) = 0

⇔

(c r
n

2

cn r 2 + cn − 1r + cn − 2 = 0 ( ya que r ≠ 0 )

+ cn − 1r + cn − 2 ) Se le llama POLINOMIO CARACTERÍSTICO

Según las raíces del polinomio característico las soluciones de las ecuaciones de recurrencia
pueden ser de dos tipos:
n
n
• 2 raíces distintas: r1 y r2 (reales o complejas), entonces la solución es an = α r1 + β r2
n
n
• Raíces...