Relaciones de Recurrencia

Ebner Pineda

Departamento de Matemáticas
Facultad de Ciencias Naturales y Matemáticas
Escuela Superior Politécnica del Litoral

20 de Junio de 2019
Tópicos de la clase

Relaciones de Recurrencia
Tópicos de la clase

Relaciones de Recurrencia

Solución de Relaciones de Recurrencia

Relación de Recurrencia

Definición.
Sea (an ) una sucesión en un conjunto X.
I Una relación de recurrencia para (an ) es una ecuación que
relaciona el término an con algunos de sus predecesores
a0 , a1 , ..., an−1 .
I Esto es an = f (an−1 , an−2 , . . . , an−k )
I Las condiciones iniciales para (an ) son valores dados en forma
explícita para un número finito de términos de la sucesión.

Ejemplo.
La sucesión de Fibonacci está definida por la relación de recurrencia
fn = fn−1 + fn−2 , n ≥ 3, y la condiciones iniciales
f1 = 1, f2 = 1.
Relación de Recurrencia

Definición.
Sea (an ) una sucesión en un conjunto X.
I Una relación de recurrencia para (an ) es una ecuación que
relaciona el término an con algunos de sus predecesores
a0 , a1 , ..., an−1 .
I Esto es an = f (an−1 , an−2 , . . . , an−k )
I Las condiciones iniciales para (an ) son valores dados en forma
explícita para un número finito de términos de la sucesión.

Ejemplo.
La sucesión de Fibonacci está definida por la relación de recurrencia
fn = fn−1 + fn−2 , n ≥ 3, y la condiciones iniciales
f1 = 1, f2 = 1.
Más adelante, daremos una fórmula explícita para esta sucesión.
Fibonacci

Figura: Serie de Fibonacci

Interés Compuesto
Ejemplo.
Una persona invierte 1000$, al 12 % de interés anual compuesto. Si
An representa la cantidad al final de n años, encuentre una relación
de recurrencia y las condiciones iniciales que definen la sucesión
(An ).

Solución:
Al final de n − 1 años, la cantidad es An−1 . Después de un años
más, se tendrá la cantidad de An−1 más el interés, entonces
An = An−1 + (0, 12)An−1 = (1, 12)An−1 , n ≥ 1.
Como A0 es la cantidad inicial, se tiene el valor inicial A0 = 1000.
Ahora, A1 = (1, 12)A0 = (1, 12)1000
A2 = (1, 12)A1 = (1, 12)2 1000 y así, sucesivamente.
Por lo que, An = (1, 12)n 1000, ∀n ∈ N.
Interés Compuesto
Ejemplo.
Una persona invierte 1000$, al 12 % de interés anual compuesto. Si
An representa la cantidad al final de n años, encuentre una relación
de recurrencia y las condiciones iniciales que definen la sucesión
(An ).

Solución:
Al final de n − 1 años, la cantidad es An−1 . Después de un años
más, se tendrá la cantidad de An−1 más el interés, entonces
An = An−1 + (0, 12)An−1 = (1, 12)An−1 , n ≥ 1.
Como A0 es la cantidad inicial, se tiene el valor inicial A0 = 1000.
Ahora, A1 = (1, 12)A0 = (1, 12)1000
A2 = (1, 12)A1 = (1, 12)2 1000 y así, sucesivamente.
Por lo que, An = (1, 12)n 1000, ∀n ∈ N.

Observaciones.
Este método de hallar una fórmula explícita para el término
n−ésimo, usando la relación de recurrencia se conoce como
método iterativo.
Torre de Hanoi

Ejemplo.
I Nunca un disco más
I Juego que consiste en
grande puede ponerse
tres estacas montadas en
encima de otro más
una tabla y n discos de
pequeño.
varios tamaños con
I Dado n, el número de
agujeros en sus centros.
I Todas la piezas apiladas discos, se desea calcular
cn , la cantidad de
en orden.
I Mover todas las piezas movidas.
apiladas en orden en otra
estaca.
I Se mueve un solo disco a
la vez de una estaca a
otra. Figura: Torre Hanoi.
Ejemplo.

●
Caso n = 1 ●
Caso n = 3
a2

Fuente: https://brilliant.org
a1 = 1
●
Caso n = 2

a2

a2 = 3 a3 = 7 = 2a2 + 1

Figura: Movimientos para la Torre de Hanoi, con n = 1, 2, 3.

Ejemplo.
I Si se tienen n > 1, discos apilados en la estaca 1.
I Se requieren cn−1 movimientos para apilar los n − 1 discos
superiores en la estaca 2.
I Un movimiento para llevar el disco restante de la estaca 1 a la
estaca 3.
I Y nuevamente cn−1 movimientos para llevar los n − 1 discos
superiores de la estaca 2 a la 3.
I Hemos apilado los n discos en la estaca 3 y se realizaron
cn = 2cn−1 + 1 movimientos.
I Relación de recurrencia, cn = 2cn−1 + 1, n > 1 y la condición
inicial c1 = 1.
Ejemplo.
Usando el método iterativo,

cn = 2cn−1 + 1 = 2(2cn−2 + 1) + 1
= 22 cn−2 + 2 + 1
= 22 (2cn−3 + 1) + 2 + 1
= 23 cn−3 + 22 + 2 + 1
..
.
= 2n−1 c1 + 2n−2 + · · · + 2 + 1
= 2n−1 + 2n−2 + · · · + 2 + 1 (suma geometrica)
1 − 2n
= = 2n − 1
1−2
Por lo que cn = 2n − 1, ∀n ∈ N.
Ejemplo.
Usando el método iterativo,

cn = 2cn−1 + 1 = 2(2cn−2 + 1) + 1
= 22 cn−2 + 2 + 1
= 22 (2cn−3 + 1) + 2 + 1
= 23 cn−3 + 22 + 2 + 1
..
.
= 2n−1 c1 + 2n−2 + · · · + 2 + 1
= 2n−1 + 2n−2 + · · · + 2 + 1 (suma geometrica)
1 − 2n
= = 2n − 1
1−2
Por lo que cn = 2n − 1, ∀n ∈ N.

Observaciones.
Se puede probar que la solución mostrada es optima
Relación de Recurrencia
Definición.
I Una relación de recurrencia homogénea lineal de orden k con
coeficientes constantes, es una relación de recurrencia de la
forma:
an = c1 an−1 + c2 an−2 + · · · + ck an−k , ck 6= 0.
I Una relación de recurrencia no homogénea, lineal de orden k
con coeficientes constantes, es una relación de recurrencia de
la forma:
an = c1 an−1 + c2 an−2 + · · · + ck an−k + h(n), ck 6= 0.

Observaciones.
I Una relación de recurrencia homogénea lineal de orden k con
coeficientes constantes, junto con k condiciones iniciales
a0 = C0 , a1 = C1 , · · · , ak−1 = Ck−1 , determina de manera
única la sucesión (an ).
I Estudiaremos solamente en este curso relaciones de recurrencia
homogénea lineales.
Ejemplo.
1. Sn = 2Sn−1 , n ∈ N, es una relación de recurrencia homogénea
lineal de orden 1 con coeficientes constantes.
2. fn = fn−1 + fn−2 , n ≥ 3, para la sucesión de Fibonacci, es
una relación de recurrencia homogénea lineal de orden 2 con
coeficientes constantes.
3. an = 3an−1 an−2 , n ≥ 3, no es una relación de recurrencia
homogénea lineal con coeficientes constantes ya que an−1 y
an−2 están multiplicando.
4. an = an−1 + 2n, n ≥ 2 no es una relación de recurrencia
homogénea lineal con coeficientes constantes, ya que el
término 2n debería ser 0. (estas relaciones se llaman
no-homogéneas)
5. an = 5an−1 + 6an−2 , n ≥ 3 es una relación de recurrencia
homogénea lineal de orden 2 con coeficientes constantes.
Solución de Relaciones de Recurrencia

Teorema.
Sea

an = c1 an−1 + c2 an−2 (1)

una Re. Re. homogénea lineal de orden 2, con coeficientes

constantes. Si S y T son sucesiones solución de (1), entonces
U = bS + cT también es solución de (1), para cualesquiera b, c ∈ R.
Si r es solución de

t2 − c1 t − c2 = 0 (2)

entonces la sucesión (rn ) es solución de (1).

Si (an ) es la sucesión determinada por (1) y las condiciones
iniciales a0 = C0 , a1 = C1 y r1 , r2 son raíces de (2) con r1 6= r2
entonces existen constantes b, c tales que an = br1n + cr2n , ∀n ∈ N.
Demostración:
Supongamos que S = (Sn ) y T = (Tn ) son solución de (1), dados
b y c constantes cualesquiera, hagamos U = bS + cT

Un = bSn + cTn = b(c1 Sn−1 + c2 Sn−2 ) + c(c1 Tn−1 + c2 Tn−2 )

= c1 (bSn−1 + cTn−1 ) + c2 (bSn−2 + cTn−2 )
= c1 Un−1 + c2 Un−2

Por lo que, U es solución de (1).

Demostración:
Supongamos que S = (Sn ) y T = (Tn ) son solución de (1), dados
b y c constantes cualesquiera, hagamos U = bS + cT

Un = bSn + cTn = b(c1 Sn−1 + c2 Sn−2 ) + c(c1 Tn−1 + c2 Tn−2 )

= c1 (bSn−1 + cTn−1 ) + c2 (bSn−2 + cTn−2 )
= c1 Un−1 + c2 Un−2

Por lo que, U es solución de (1).

Ahora, si r es solución de t2 − c1 t − c2 = 0 entonces r2 = c1 r + c2 ,
multiplicando por rn−2 tenemos rn = c1 rn−1 + c2 rn−2 , n ∈ N, esto
es, la sucesión (rn ) es solución de (1).
Demostración:
Supongamos que S = (Sn ) y T = (Tn ) son solución de (1), dados
b y c constantes cualesquiera, hagamos U = bS + cT

Un = bSn + cTn = b(c1 Sn−1 + c2 Sn−2 ) + c(c1 Tn−1 + c2 Tn−2 )

= c1 (bSn−1 + cTn−1 ) + c2 (bSn−2 + cTn−2 )
= c1 Un−1 + c2 Un−2

Por lo que, U es solución de (1).

Ahora, si r es solución de t2 − c1 t − c2 = 0 entonces r2 = c1 r + c2 ,
multiplicando por rn−2 tenemos rn = c1 rn−1 + c2 rn−2 , n ∈ N, esto
es, la sucesión (rn ) es solución de (1).
Finalmente, si r1 y r2 son raíces distintas de (2), por lo anterior,
(r1n ) y (r2n ) son soluciones de (1) en consecuencia , la sucesión U
dada por Un = br1n + cr2n también es solución de (1) para
cualesquiera constantes b, c.
Demostración:
Si hacemos, C0 = b + c y C1 = br1 + cr2
multiplicando la primera ecuación por r1 y luego restamos la
segunda obtenemos
r1 C0 − C1 = (r1 − r2 )c y como r1 6= r2 , se tiene que
r1 C0 − C1 r1 C0 − C1
c= y en consecuencia b = C0 − c = C0 −
r1 − r2 r1 − r2
Esto es, con estos valores particulares de b y c, tenemos que U es
solución de (1) con condiciones iniciales U0 = C0 , U1 = C1 ,
por unicidad, an = Un = br1n + cr2n , ∀n ∈ N.
Ejemplo.
Suponga que la población de venados del condado Rustic es, 200
en el tiempo n = 0, y 220 en el tiempo n = 1, además el
incremento del tiempo n − 1 al tiempo n es dos veces el incremento
del tiempo n − 2 al tiempo n − 1. Escriba la relación de recurrencia
y una condición inicial que define la población de venados en el
tiempo n y después resuelva la relación de recurrencia.
Solución:
I Sea dn la población de venados en el tiempo n. Se tienen las
condiciones iniciales d0 = 200, d1 = 220.
I El incremento del tiempo n − 1 al tiempo n es dn − dn−1 , y el
incremento del tiempo n − 2 al tiempo n − 1 es dn−1 − dn−2 .
Entonces se obtiene la relación de recurrencia
dn − dn−1 = 2(dn−1 − dn−2 ), la cual se re-escribe como
dn = 3dn−1 − 2dn−2 .
I Usando el teorema, resolvemos la ecuación t2 − 3t + 2 = 0,
con raíces r1 = 1 y r2 = 2.
I La solución es de la forma dn = b · 1n + c · 2n = b + c · 2n ,
n ∈ N.
I Por las condiciones iniciales tenemos que 200 = d0 = b + c y
220 = d1 = b + 2c, por lo que b = 180 y c = 20.
I Esto es dn = 180 + 20 · 2n , ∀n ∈ N.
Sucesión de Fibonacci
Ejemplo.
Para la sucesión de Fibonacci, fn = fn−1 + fn−2 , n ∈ N,
resolvemos,
√ √
2 1+ 5 1− 5
t − t − 1 = 0 y obtenemos las raíces r1 = y r2 =
2 2
√ !n √ !n
1+ 5 1− 5
Así, fn es de la forma fn = b +c .
2 2
√ ! √ !
1+ 5 1− 5
Por las condiciones iniciales 1 = f1 = b +c
2 2
y
√ !2 √ !2
1+ 5 1− 5
1 = f2 = b +c
2 2
1 1
De donde se obtiene que b = √ y c = − √
5 5
√ !n √ !n
1 1+ 5 1 1− 5
Esto es, fn = √ ( −√ , ∀n ∈ N.
5 2 5 2
Teorema.
Sea

an = c1 an−1 + c2 an−2

una relación de Re. Re, como (1) de orden 2, con coeficientes

constantes y sea (an ) la solución de (1) junto con las condiciones
iniciales a0 = C0 y a1 = C1 .
Si ambas raíces de

t2 − c1 t − c2 = 0 (3)

son iguales a r entonces existen constantes b y c tales que

an = brn + c n rn , ∀n ∈ N.
Ejemplo.
Resolver la relación de recurrencia dn = 4dn−1 − 4dn−2 ,
con condiciones iniciales d0 = d1 = 1

Solución:
La ecuación t2 − 4t + 4 = 0 tiene sólo una raíz r = 2
Por el teorema anterior, existen constantes b y c, tales que
dn = b2n + cn2n , n ∈ N
y por las condiciones iniciales
1 = d0 = b + c · 0 = b
1 = d1 = 2b + 2c
Obtenemos que, b = 1 y c = −1/2
1
Por lo que, dn = 2n − n2n = 2n − n2n−1 , ∀n ∈ N.
2
Ejemplo.
Resolver la relación de recurrencia
an = 6an−1 − 8an−2 , con condiciones iniciales a0 = 1, a1 = 0

Solución:
La ecuación t2 − 6t + 8 = 0 tiene dos raíces distintas r1 = 4, r2 = 2
Por el teorema sobre las dos soluciones, existen constantes b, c tales
que an = b4n + c2n , n ∈ N
y por las condiciones iniciales
1 = a0 = b + c
0 = a1 = 4b + 2c
Así, b = −1 y c = 2
Por lo que, an = −4n + 22n = −4n + 2n+1 , ∀n ∈ N.
Ejemplo.
Resolver la relación de recurrencia
an = 6an−1 − 9an−2 , con condiciones iniciales a0 = a1 = 1

Solución:
La ecuación t2 − 6t + 9 = 0 tiene sólo una raíz r = 3
Por el teorema sobre la solución con una sola raíz, existen
constantes b, c tales que an = b3n + cn3n , n ∈ N
y por las condiciones iniciales
1 = a0 = b + c · 0 = b
1 = a1 = 3b + 3c
Así, b = 1 y c = −2/3
2
Por lo que, an = 3n − n3n = 3n − 2n3n−1 , ∀n ∈ N.
3