Unidad 3 / Escenario 5

Lectura fundamental

Ecuaciones de recurrencia

Contenido

1 Ecuaciones de recurrencia

2 Ecuaciones de recurrencia lineales homogéneas

3 Ecuaciones de recurrencia lineales no homogéneas

4 Ejercicios

Bibliografı́a

Palabras claves:
Ecuación de recurrencia, ecuación de recurrencia lineal, polinomio característico
Introducción

Existen algoritmos que requieren el uso de funciones definidas de forma recursiva o generar una secuencia de datos
(relacionados de forma recursiva). Ejemplos de ello es el método de ordenamiento merge sort, el método de solución
de ecuaciones de Newton o el método de búsqueda binaria; empleados en campos como inteligencia artificial y
matemáticas. En esta lectura se presentan herramientas para analizar la complejidad de este tipo de algoritmos.

1. Ecuaciones de recurrencia

Observe las siguientes secuencias de números:

• 1, 2, 4, 8, 16, 32, 64, 128, 256, . . .

• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
• 4, 6, 2, 14, 10, 18, 38, 2, . . .

En cada caso, ¿puede hallar un término más de la sucesión? En la primera lista, se observa que cada elemento de
la secuencia (a partir de la segunda posición) es el doble del anterior, por lo tanto el término que sigue a 256 es
512; en la seguna lista al analizar sus elementos se concluye que cada término (a partir del tercero) es la suma de
los dos términos anteriores ⇤ por lo cuál el número que sigue a 34 es 55 = 34 + 21.

Si en una sucesión cada término, a partir de una posición, se obtiene a través de un cálculo que emplea elementos
de la secuencia ubicados en posiciones anteriores entonces se dice que existe una relación de recurrencia entre los
elementos. Las sucesiones presentadas anteriormente son un ejemplo de ello.

Si los elementos de la suceción 1, 2, 4, 8, 16, 32, 64, 128, 256, . . . se denotan por a0 , a1 , a2 , a3 , . . . respectivamente,
entonces la relación de recurrencia para esta secuencia se podrı́a expresar de la siguiente forma:
an = 2an 1 para n 1 (1)
Que corresponde a l a i dea “cada elemento, a partir de l a posición 1, de l a secuencia se obtiene multiplicando por 2 el
elemento que está en la posición anterior”. El lector debe notar que la relación (1) está definida para n 1 dado que
a0 = 1 corresponde al primer término de la sucesión y sobre este no tiene sentido la relación de recurrencia,
además este elemento corresponde a la condición inicial para generar los otros elementos.

Si se simbolizan los términos de la sucesión 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . como b0, b1, b2, . . . respectivamente,
entonces la relación de recurrencia presente en esta sucesión se expresa de la forma:
bn = bn 1 + bn 2 para n 2 (2)
⇤
Esta es la sucesión de Fibonacci.

POLITÉCNICO GRANCOLOMBIANO 1
Y su condición i nicial es b 0 =0, b 1 =1. Debe tener presente que el símbolo b n 1 hace r eferencia al elemento que está en
la posición anterior a bn y bn 2 denota al elemento que se ubica dos posiciones antes del elemento bn. A través de la
siguiente definición se formalizan las ideas expuestas anteriormente.

Definición 1. Una relación de recurrencia entre los elementos de una sucesión c0 , c1 , c2 , . . . es una ecuación
que establece una relación entre un elemento cn de la secuencia y los elementos que lo preceden.

Observe que aunque exista una relación de recurrencia en los términos de una sucesión, no todos sus elementos se
pueden calcular a través de ella. Por lo tanto, es necesario establecer algunos términos de forma explı́cita, los cuales
se denominan la condición inicial de la recurrencia. Por ejemplo, si los términos de una secuencia satisfacen la
relación:

cn = cn 1 cn 2 para n 2

Entonces, cada término a partir de la posición n = 2 se obtiene realizando la resta de los términos anteriores, pero los
términos c0 y c1 no son calculables a través de esta relación, por lo tanto es necesario indicar explı́citamente su valor.
Ası́, que una definición completa de la sucesión cn es:
(
c0 = 5
Condición inicial:
c1 = 3
Relación de recurrencia: {cn = cn 1 cn 2 para n 2

A continuación se exponen ejemplos de sucesiones definidas por una relación de recurrencia. Lo invito a revisar cada
uno con detalle.

Ejemplo 1. Sea (fn ) la sucesión definida por la relación fn = fn2 1 1 para n 1 y condición inicial f0 = 0.
Calcular el término f2.

Solución: Para hallar f2 se debe emplear la relación de recurrencia, que para este caso indica que:

f2 = f12 1

Pero se desconoce el valor de f1, entonces se debe calcular primero este dato. Para lo cual se emplea de nuevo la
relación de recurrencia, por lo tanto:
f1 = f02 1
el valor de f0 es 0, condicion inicial, con lo cual:

f1 = 02 1= 1

y conociendo que f1 = 1 se puede determinar f2 :

f2 = ( 1)2 1=0

POLITÉCNICO GRANCOLOMBIANO 2
Ejemplo 2. Sea (an ) la sucesión definida por la relación an = an 2 an 3 para n 3 y condición inicial a0 = 1,
a1 = 4, a2 = 7. Calcular el término a4 .

Solución: Para determinar el valor de a4 se debe emplear la relación de recurrencia, que para esta posición
establece que:
a4 = a2 a1
como a2 y a1 son condición inicial de la sucesión, entonces sus valores son conocidos y por lo tanto se tiene que:

a4 = 4 1=3

Ejemplo 3. Sea (bn ) la sucesión definida por la relación bn = bn 1 + bn 3 + bn 5 para n 5 y condición inicial
b0 = 1, b1 = 2, b2 = 2, b3 = 1, b4 = 0. Calcular el término b6.

Solución: para determinar el valor de b6 se debe emplear la relación de recurrencia, que para esta posición
establece que:
b6 = b5 + b3 + b1
Como b3 y b1 son condición inicial de la sucesión, entonces sus valores son conocidos. Pero el valor de b5 no se
tiene, por lo tanto se debe hallar primero este valor para lo cual se utiliza la relación de recurrencia que indica
que:

b5 = b4 + b2 + b0

Aquı́ b4, b2 y b0 son condiciones iniciales entonces se conoce su valor. Ası́ que,

b5 = 0 + ( 2) + 1 = 1

Ahora, se puede determinar el valor de b6:

b6 = b5 + b3 + b1
= 1 + ( 1) + 2 = 0

Los ejemplos anteriores, permiten exponer el uso de la relación de recurrencia y sus condiciones iniciales para hallar
nuevos términos de una sucesión. Como se puede notar, si se desea calcular un término que está en una posición
alta es necesario utilizar varios términos previos, lo que computacionalmente puede ser costoso; por lo tanto una
pregunta natural es: dada una sucesión (cn ) definida por una relación de recurrencia, ¿existe una fórmula que
permita hallar el valor de cn sin tener que recurrir a elementos previos en la sucesión? En lo que sigue se exponen
las situaciones donde es posible determinar una fómula explı́cita para la suceción.

Dependiendo del tipo de relación de recurrencia se pordrá seguir un proceso que permita sustituir la ecuación de
recurrencia por una relación explı́cita entre un término de la sucesión y su posición sin utilizar elementos previos
de la secuencia. Por lo tanto, es importante para el lector, identificar los tipos de relaciones de recurrencia y sus
métodos de solución.

POLITÉCNICO GRANCOLOMBIANO 3
2. Ecuaciones de recurrencia lineales homogéneas

Definición 2. Una relación de recurrencia es una ecuación de recurrencia lineal homogénea con coeficientes
constantes de orden k si es de la forma:

an = c 1 an 1 + c 2 an 2 + c 3 an 3 + · · · + c k an k con ck 6= 0

donde ci 2 R es constante para i = 1, 2, . . . , k.

Es decir, el término de la posición n equivale a la combinación lineal de los elementos que están k posiciones atrás. Es
importante destacar que en una relación de recurrencia lineal homogénea de orden k no siempre se hace uso de todos
los k 1-anteriores elementos. Para simplificar la escritura se dirá a una ecuación de recurrencia lineal homogenea
con coeficientes constantes de orden k, ecuación de recurrencia lineal homogénea.

Observe a continuación los siguientes ejemplos de relaciones de recurrencia y por qué son o no ecuaciones
de recurrencia lineal homogénea.
Ejemplo 4. Sea la relación de recurrencia:
an = 3an 1

Entonces esta es una ecuación de recurrencia lineal homogénea de orden 1 (es necesario el elemento que está en la
posición anterior).
Ejemplo 5. Sea la relación de recurrencia:
fn = fn2 1
Entonces esta no es una ecuación de recurrencia lineal homogénea, dado que para calcular el término de la posición n
es necesario elevar al cuadrado el elemento que está en la posición n 1
Ejemplo 6. Sea la relación de recurrencia:

bn = bn 1 + bn 3 + bn 5

Entonces esta es una ecuación de recurrencia lineal homogénea de orden 5 (la posición más pequeña necesaria para
calcular bn está cinco posiciones atrás).
Ejemplo 7. Sea la relación de recurrencia:

bn = bn 1bn 3 + bn 5

Entonces esta no es una ecuación de recurrencia lineal homogénea, dado que existe una multiplicación entre los
términos de las posiciones n 1 y n 3.
Ejemplo 8. Sea la relación de recurrencia:

bn = 3bn 1+ 2bn 3 + bn 4 + n

Entonces esta no es una ecuación de recurrencia lineal homogénea, dada la presencia del sumando n en la expresión
del lado derecho de la ecuación.

En una ecuación de recurrencia lineal homogénea solo se puede hacer uso de los términos previos de la sucesión.

POLITÉCNICO GRANCOLOMBIANO 4
Ejemplo 9. Sea la relación de recurrencia:

dn = dn 1 5dn 3+ dn 4+ 1

Entonces esta no es una ecuación de recurrencia lineal homogénea, dada la presencia del sumando 1 en la expresión
del lado derecho de la ecuación.

Ejemplo 10. Sea la relación de recurrencia:

cn = cn 2 5cn 3 + cn 4

Entonces esta es una ecuación de recurrencia lineal homogénea de orden 4.

Ejemplo 11. Sea la relación de recurrencia:

cn = cn 2 5cn 3+ ncn 4

Entonces esta no es una ecuación de recurrencia lineal homogénea, dado que el coeficiente de cn 4 no es constante.

2.1. Ecuaciones de primer orden

Observe la siguiente ecuación de recurrencia lineal homogénea de orden 1 ( o primer orden):

an = 5an 1 para n 1

Con condicion inicial a0 = 7. Los primeros 5 términos son:

a0 = 7
a1 = 5a0 = 5(7)
a2 = 5a1 = 5(5(7)) = 52 (7)
a3 = 5a2 = 5(52 (7)) = 53 (7)
a4 = 5a3 = 5(53 (7)) = 54 (7)

Lo que sugiere que an = 7(5n) para n 0. Esta relación corresponde a una fórmula explı́cita para calcular un término
de la sucesión. Si se desea calcular a10 solo es necesario evalúar 7(510) = 68.359.375 sin necesidad de conocer los t
érminos a9, a8, a7, . . .. El siguiente teorema indica la forma de construir la relación explı́cita de una ecuación de
recurrencia lineal homogénea de primer orden.

Teorema 1. La relación explı́cita de la ecuación de recurrencia lineal homogénea de primer orden:

an = C · an 1 para n 1

con condición inicial a0 = D es:

an = D · (C)n para n 0

Es tradicional denominar la relación explícita como la solución de la ecuación de recurrencia.

POLITÉCNICO GRANCOLOMBIANO 5
Ejemplo 12. Determinar la solución de la ecuación de recurrencia:

bn = 2bn 1 para n 1

con condición inicial b0 = 5. Luego hallar b7

Solución: como la ecuación de recurrencia es lineal homogénea de primer orden, entonces por el teorema anterior
se tiene que:
bn = 5( 2)n
y por lo tanto b7 = 5( 2)7 = 640 }

Ejemplo 13. En un laboratorio se está estudiando el crecimiento de una batería particular. Los experimentos
han evidenciado que la población de este microorganismo crece un 3 % cada día, con relación a la población del
día anterior, cuando están en un ambiente limpio y sin presencia de otras bacterias. Determinar cuántas bacterias
hay después de 10 días si la población inicial corresponde a 1200 bacterias.

Solución: si se denota por pn la población de bacterias que hay después de n dı́as, entonces la relación de crecimiento
se puede expresar de la forma:
pn = 1.03pn 1
y la población inicial corresponde a p0 , es decir p0 = 1200.

Como esta es una relación de recurrencia lineal homogénea de primer orden entonces se tiene que:

pn = 1200(1.03)n

Con lo cual, después de 10 dı́as hay una población de p10 = 1200(1.03)10 ⇡ 1613 bacterias. }

Ejemplo 14. Dada la sucesión 12, 6, 3, 32 , 34 , . . .. Determine el término que se ubica en c100 si denotamos los
elementos de la secuencia por c0, c1, c2, c3, . . . respectivamente.

Solución: al analizar la sucesión se observa que hay la siguiente relación de recurrencia entre sus elementos:
1
cn = cn 1 para n 1
2
Con condición inicial c0 = 12. Por lo tanto, la solución de la ecuación es:
✓ ◆n
1
cn = 12
2

1 100 30
ası́ que c100 = 12 2 ⇡ 9, 47 ⇥ 10 }

2.2. Ecuaciones de segundo orden

Considere la siguiente ecuación de recurrencia lineal homogénea de segundo orden:

cn = 2cn 1 + 3cn 2

con c0 = 1 y c1 = 5.

POLITÉCNICO GRANCOLOMBIANO 6
¿Cómo hallar una relación explı́cita a partir de esta ecuación? Siguiendo la idea de lo obtenido en las ecuaciones
lineales homogéneas de primer orden, se puede suponer que la relación explı́cita de esta ecuación es de la forma:
cn = k · r n (3)
Con k y r números diferentes a cero. Por lo tanto, el problema ahora consiste en determinar el valor de k y r
correctos. Si se sustituye (3) en la ecuación cn = 2cn 1 + 3cn 2 se obtiene que

k · rn = 2k · rn 1
+ 3k · rn 2

que es equivalente a la ecuación:

krn 2krn 1
3krn 2
=0
factorizando krn 2 se obtiene:
krn 2
(r2 2r 3) = 0
y como k y r son valores diferentes a cero, entonces se concluye a partir de esta última ecuación que:
r2 2r 3=0 (4)
La ecuación (4) se denomina la ecuación caracterı́stica de la recurrencia cn = 2cn 1 + 3cn 2. Al resolver esta
ecuación† se obtiene que:
r=3 o r= 1
Es decir, existen dos soluciones de la ecuación de recurrencia:
c n = k 1 · 3n o cn = k2 · ( 1)n
El lector puede verificar que tomando solo una de las soluciones, por ejemplo cn = k1 · 3n , no es posible satisfacer
las dos condiciones iniciales, dado que c0 = 1 y si c0 = k1 · 30 = k1 entonces k1 = 1, luego cn = 1(3)n pero al
evaluar c1 se obtiene c1 = 3 que es distinto a la condición inicial.

Por lo tanto, se considera la solución‡

cn = k1 · 3n + k2 · ( 1)n
Para hallar los valores de k1 y k2 se evalúa la expresión anterior en las posiciones de la condición inicial n = 0 y
n = 1, luego se iguala a lo valores dados c0 = 1 y c1 = 5:
c0 = k1 · 30 + k2 · ( 1)0 = k1 + k2
c1 = k1 · 31 + k2 · ( 1)1 = 3k1 k2

por lo tanto:
k1 + k2 = 1
3k1 k2 = 5

1
Resolviendo este sistema de ecuaciones, se concluye que k1 = 23 y k2 = 2. Ası́ que la solución de la ecuación de
recurrencia cn = 2cn 1 + 3cn 2 con c0 = 1 y c1 = 5 es
3 n 1
cn = ·3 · ( 1)n para n 0
2 2

Lo realizado anteriormente se puede resumir en el siguiente teorema:

†
puede emplear la fórmula cuadrática, estudiada en sus módulos de matemáticas
‡
Se puede demostrar que esta relación es también solución de la ecuación homogénea

POLITÉCNICO GRANCOLOMBIANO 7
 Teorema 2. Dada la ecuación de recurrencia lineal homogénea de segundo orden con coeficientes constantes:

an + c1an 1 + c2an 2 = 0

Si la ecuación caracterı́stica asociada:

r2 + c1r + c2 = 0
Tiene dos soluciones reales distintas r1 y r2. Entonces la solución de la recurrencia es de la forma:

an = k1r1n + k2r2n

Los valores de k1 y k2 se determinan empleando las condiciones iniciales de la relación de recurrencia.

Ejemplo 15. Determinar la solución de la ecuación de recurrencia bn = 5bn 1 6bn 2 con condición inicial b0 = 0,
b1 = 2.

Solución: esta es una ecuación de recurrencia de segundo orden, por lo tanto se intetará aplicar el teorema anterior.
Lo primero que se debe hacer es igualar a cero la relación de recurrencia bn = 5bn 1 6bn 2, lo que corresponde a:
bn 5bn 1 + 6bn 2 = 0
Luego, se determina la ecuación caracterı́stica de esta relación, que para este ejemplo corresponde a:

r2 5r + 6 = 0

(Observe con detalle la ecuación caracterı́stica y la ecuación de recurrencia igualada a cero). Al solucionar la
ecuación caracterı́stica se obtiene:
r=2 o r=3
como son dos soluciones distintas y reales, se concluye que la solución de la recurrencia es de la forma:

bn = k1(2)n + k2(3)n (5)

Para determinar los valores de k1 y k2 se evalúa la expresión (5) en n = 0 y n = 1 con lo que se obtiene que:

b0 = k1 (2)0 + k2 (3)0 = k1 + k2
b1 = k1 (2)1 + k2 (3)1 = 2k1 + 3k2

Pero b0 = 0 y b1 = 2, por lo tanto:

k1 + k2 = 0
2k1 + 3k2 = 2

Resolviendo el sistema, se determina que k1 = 2 y k2 = 2. Ası́ que la solución de la ecuación de recurrencia es:

bn = 2(2)n + 2(3)n

POLITÉCNICO GRANCOLOMBIANO 8
Ejemplo 16. Determinar la solución de la ecuación de recurrencia dn = 3dn 1 + 28dn 2 con condición inicial
d0 = 1, d1 = 3.

Solución: al igualar a cero la relación de recurrencia, se obtiene

dn 3dn 1 28dn 2 =0
Por lo tanto la ecuación característica es:
r2 3r 28 = 0
y sus soluciones son:
r=7 o r= 4
Como son dos soluciones distintas y reales, se concluye que la solución de la recurrencia es de la forma:
dn = k1(7)n + k2( 4)n (6)
Para determinar los valores de k1 y k2 se evalúa la expresión (6) en n = 0 y n = 1 con lo que se obtiene

d0 = k1 (7)0 +que:
k2 ( 4)0 = k1 + k2
d1 = k1 (7)1 + k2 ( 4)1 = 7k1 4k2

Pero d0 = 1 y d1 = 3, por lo tanto:

k1 + k2 = 1
7k1 4k2 = 3

4
Resolviendo el sistema, se concluye que k1 = 117 y k2 = 11 . Ası́ que la solución de la ecuación de recurrencia es:
7 4
dn = (7)n + ( 4)n n 0
11 11
}

Ejemplo 17. Determinar la solución de la ecuación de recurrencia cn = 4cn 2 con condición inicial c0 = 1, c1 = 0.

Solución: al igualar a cero la relación de recurrencia, se obtiene

cn 4cn 2 =0

Por lo tanto la ecuación característica es:

r2 4=0
y sus soluciones son:
r=2or= 2
Como son dos soluciones distintas y reales, se concluye que la solución de la recurrencia es de la forma:
cn = k1(2)n + k2( 2)n (7)
para determinar los valores de k1 y k2 se evalúa la expresión (7) en n = 0 y n = 1 con lo que se obtiene que:

c0 = k1 (2)0 + k2 ( 2)0 = k1 + k2
c1 = k1 (2)1 + k2 ( 2)1 = 2k1 2k2

POLITÉCNICO GRANCOLOMBIANO 9
Pero c0 = 1 y c1 = 0, por lo tanto:
k1 + k2 = 1
2k1 2k2 = 0

Resolviendo el sistema, se concluye que k1 = 21 y k2 = 12 . Ası́ que la solución de la ecuación de recurrencia es:
1 1
cn = (2)n + ( 2)n n 0
2 2
}

Pero qué sucede si solo hay una solución real de la ecuación caracterı́stica o si no hay solución en los números
reales. En la primera situación se tiene:

Teorema 3. Dada la ecuación de recurrencia lineal homogénea de segundo orden con coeficientes constantes:

an + c 1 an 1 + c 2 an 2 =0

si la ecuación caracterı́stica asociada:

r 2 + c1 r + c2 = 0
tiene única solución real r. Entonces la solución de la recurrencia es de la forma:

an = k1 r n + k2 · n · r n

los valores de k1 y k2 se determinan empleando las condiciones iniciales de la relación de recurrencia.

Se debe destacar que para el caso de única solución en la ecuación caracterı́stica, se construyen dos soluciones:
k1 r n y k2 · n · r n
Ejemplo 18. Determinar la solución de la ecuación de recurrencia cn = 10cn 1 25cn 2 con condición inicial
c0 = 1, c1 = 2.

Solución: Al igualar a cero la relación de recurrencia, se obtiene

cn 10cn 1 + 25cn 2 =0
Por lo tanto la ecuación caracterı́stica es:
r2 10r + 25 = 0
y su única solución es:
r=5
entonces se concluye que la solución de la recurrencia es de la forma:
cn = k1 (5)n + k2 · n · (5)n (8)
para determinar los valores de k1 y k2 se evalúa la expresión (8) en n = 0 y n = 1 con lo que se obtiene que:
c0 = k1 (5)0 + k2 (0)(5)0 = k1
c1 = k1 (5)1 + k2 (1)(5)1 = 5k1 + 5k2

POLITÉCNICO GRANCOLOMBIANO 10
pero c0 = 1 y c1 = 2, por lo tanto:

k1 = 1
5k1 + 5k2 = 2

3
resolviendo el sistema, se concluye que k1 = 1 y k2 = 5. Ası́ que la solución de la ecuación de recurrencia es:

3
cn = 1(5)n n(5)n n 0
5
}

Ejemplo 19. Determinar la solución de la ecuación de recurrencia cn = 2cn 1 cn 2 con condición inicial
c0 = 1, c1 = 1.

Solución: al igualar a cero la relación de recurrencia, se obtiene

cn + 2cn 1 + cn 2 =0

Por lo tanto la ecuación caracterı́stica es:

r2 + 2r + 1 = 0
y su única solución es:
r= 1
Entonces, se concluye que la solución de la recurrencia es de la forma:

cn = k1( 1)n + k2 · n · ( 1)n (9)

Para determinar los valores de k1 y k2 se evalúa la expresión (9) en n = 0 y n = 1 con lo que se obtiene que:

c0 = k1 ( 1)0 + k2 (0)( 1)0 = k1

c1 = k1 ( 1)1 + k2 (1)( 1)1 = k1 k2

pero c0 = 1 y c1 = 1, por lo tanto:

k1 = 1
k1 k2 = 1

Resolviendo el sistema, se concluye que k1 = 1 y k2 = 2. Ası́ que la solución de la ecuación de recurrencia es:

cn = 1( 1)n 2n( 1)n n 0

Que es equivalente a:
cn = ( 1)n (1 2n) n 0
}

En el caso que no existan soluciones reales, se debe trabajar en el sistema de los números complejos. Se recomienda
revisar la lectura complementaria de este escenario.

POLITÉCNICO GRANCOLOMBIANO 11
3. Ecuaciones de recurrencia lineales no homogéneas

En esta sección se presenta un método para solucionar algunas ecuaciones recursivas lineales no homogéneas con
coeficientes constantes de la forma:

an + c 1 an 1 = f (n) para n 1

o de la forma

an + c1an 1 + c2an 2 = f (n) para n 2

Con f (n) una función no idénticamente cero.

(p) (h)
El método consiste en hallar una solución particular del problema an = g(n) y la solución an del problema
(h)
homogéneo asociado, para luego considerar la solución an = g(n) + an .

3.1. Solución particular de una relación de recurrencia

Cuando se tiene una relación de recurrencia de la forma:

an + c1an 1+ · · · + ckan k= f(n)

se dice que an = g(n) es una solución particular de la ecuaci´on de recurrencia si al evaluar la ecuación
se satisface la igualdad, es decir:
g(n) + c1 g(n 1) + · · · + ck g(n k) = f (n)
Ejemplo 20. Considere la siguiente ecuación de recurrencia no homogénea:

an 2an 1 = 5n

verifique que an = 53 (5)n es una solución particular de la ecuación.

Solución: Si an = 53 (5)n entonces an 1 = 53 (5)n 1, sustituyendo estos resultados en el lado derecho de la ecuación
se obtiene:

5 5
an 2an 1 = (5)n 2 (5)n 1
3 3
5 n
= (5 2(5n 1 ))
3
5
= 5n 1 (5 2)
3
5
= 5n 1 (3)
3
= 5n

con lo cual se cumple la igualdad. }

POLITÉCNICO GRANCOLOMBIANO 12
Ejemplo 21. Considere la siguiente ecuación de recurrencia no homogénea:

an 3an 1 =n
1 3
verifique que an = 2n 4 es una solución particular de esta ecuación.

Solución: Si an = 12 n 3
4 entonces an 1 = 1
2 (n 1) 3
4, sustituyendo estos resultados en el lado derecho de
la ecuación se obtiene:

✓ ◆
1 3 1 3
an 3an 1 = n 3 (n 1)
2 4 2 4
1 3 3 3
= n+ + n+
2 4 2 4
=n

con lo cual se cumple la igualdad. }

La pregunta que surge en este punto es ¿cómo hallar una solución particular de una ecuación de recurrencia no
homogénea?

Considere la siguiente ecuación de recurrencia no homogénea:

an + 7an 1 = 4n (10)

si se desea buscar una solución particular se puede suponer que la solución buscada es de la forma

an = C · 4n

es decir, tiene una forma similar a la función que está en el lado derecho de la ecuación, debido a que si an + 7an 1
debe dar igual a 4n entonces an debe ser parecida a 4n . Si se reemplaza an = C · 4n en la ecuación 10 se obtiene:

C · 4n + 7(C · 4n 1
) = 4n

factorizando C · 4n 1 del lado izquierdo, se tiene que:

C · 4n 1
(4 + 7) = 4n

dividiendo ambos lados por 4n 1:

11C = 4
4 4 n
luego C = 11 , ası́ que una solución particular de la ecuación an + 7an 1 = 4n es an = 11 4 .

La siguiente tabla da una referencia para seleccionar la forma de la solución particular, dependiendo de la forma
de la función f (n) que se presente en la ecuación de recurrencia. A, A2 , A1 , A0 representan constantes.

POLITÉCNICO GRANCOLOMBIANO 13
 Tabla 1. Estructura de una solución particular g(n)

f (n) g(n)
K constante A constante
n A1 n + A0
n2 A2 n2 + A1 n + A0
rn Arn

Fuente: elaboración propia

Para entender el uso de la tabla anterior, revise el siguiente ejemplo:

Ejemplo 22. Determinar una solución particular de la ecuación de recurrencia an = 4an 2 + 2n.

Solución: Primero se organiza la ecuación an = 4an 2 +2n, dejando los términos que hacen referencia a elementos
de la sucesión a un solo lado de la igualdad:

an 4an 2 = 2n

por lo tanto la función f (n) de esta ecuación no homogénea es f (n) = 2n. Al revisar la tabla 1 se obtiene que
si f (n) es similar a n entonces la solución particular an = g(n) puede ser de la forma an = A1 n + A0 . Ahora,
sustituyendo en la ecuación de recurrencia se obtiene:

an 4an 2 = A1 n + A0 4(A1 (n 2) + A0 )
= 3A1 n 3A0 + 8A1

2 16
e igualando a 2n se concluye que A1 = 3 y A0 = 9 , por lo tanto la solución particular de la ecuación de
recurrencia es:
2 16
an = n
3 9
}

3.2. Solución de una ecuación no homogénea

Luego de presentar un método para determinar una solución particular de una ecuación no homogénea, se expone
el siguiente procedimiento para hallar la solución de una ecuación no homogénea.

POLITÉCNICO GRANCOLOMBIANO 14
 Si se tiene una ecuación de recurrencia de la forma:

an + c 1 an 1 + · · · + ck an k = f (n)

entonces para hallar su solución se puede realizar lo siguiente:

(h)
1) Determinar la solución an de la ecuación de recurrencia homogénea asociada, es decir:

an + c 1 an 1 + · · · + c k an k =0

2) Hallar una solución particular an = g(n) de la ecuación no homogénea.

an + c 1 an 1 + · · · + ck an k = f (n)

(h)
3) Construir la solución an = g(n) + an

Ejemplo 23. Determinar la solución de la ecuación an = 4an 2 + 2n.

Solución: En este caso la ecuación no homogénea correspondiente es:

an 4an 2 = 2n

con lo cual la ecuación homogénea asociada es:

an 4an 2 =0

cuya solución es:

a(h) n
n = k1 2 + k2 ( 2)
n

Ahora, una solución particular de an 4an 2 = 2n se calculó en la sección anterior:

2 16
a(p)
n = n
3 9
Luego la solución de la ecuación de recurrencia es:
2 16
an = k1 2n + k2 ( 2)n n
3 9
para hallar los valores de k1 y k2 se hace uso de las condiciones iniciales. }
Ejemplo 24. Determinar la solución de la ecuación an + 7an 1 = 4n .

Solución: En este caso la ecuación homogénea asociada es:

an + 7an 1 =0

cuya solución es:

a(h)
n = k( 7)
n

Ahora, una solución particular de an 4an 2 = 2n se calculó anteriormente:

4n+1
a(p)
n =
11

POLITÉCNICO GRANCOLOMBIANO 15
Luego la solución de la ecuación de recurrencia es:

4n+1
an = k( 7)n +
11
para hallar el valor de k se hace uso de la condición inicial. }

POLITÉCNICO GRANCOLOMBIANO 16
4. Ejercicios

Los siguientes ejercicios tienen como objetivo que el estudiante afiance los conceptos presentados en la lectura, no se
deben entregar al tutor del m´odulo.

1. Determine los primeros 5 términos de la sucesión definida por la relación de recurrencia an = 1 3 an 1 +1

con la condición inicial a0 = 1.

2. Determine si la relación de recurrencia cn = cn 1 + cn 2 1 es una relación homogénea.

3. Halle una relación de recurrencia para la sucesión 4, 6, 2, 14, 10, 18, . . .

4. Determine la solución de la ecuación de recurrencia dn = 12 dn 1 para n 1 con d0 = 32

5. Determine la solución de la ecuación de recurrencia fn = fn 1 + fn 2 para n 2 con f0 = 0, f1 = 1. [Esta

es la sucesión de Fibonacci clásica]

6. Determine la solución de la ecuación de recurrencia fn = fn 1 + fn 2 para n 2 con f0 = 0, f1 = 1. [Esta

es una modificación de la sucesión de Fibonacci]

7. Determine la solución de la ecuación de recurrencia an = 6an 1 9an 2 para n 2 con a0 = 1 y a1 = 2

8. Determine una solución particular de la ecuación de recurrencia an = 5an 1 4an 2 + 3n

9. Determine una solución particular de la ecuación de recurrencia an = 2an 1 + n2

10. Determine la solución de la ecuación de recurrencia an = 5an 1 4an 2 + 3n con a0 = 1 y a1 = 5

Bibliografı́a

[1] Grimaldi, R. (1998) Matemáticas discreta y combinatoria. México: Addison-Wesley Iberoamericana.

[2] Hammack, R. (2013) Book of proof, second edition, Editor: Richard Hammack.

[3] Rosen, K.H. and Pérez, J.M. (2004) Matemática discreta y sus aplicaciones, Madrid: McGraw-Hill.

POLITÉCNICO GRANCOLOMBIANO 17
 INFORMACIÓN TÉCNICA

Módulo: Elementos en Teorı́a de la Computación

Unidad 3: Introducción al análisis de algoritmos
Escenario 5: Relaciones y funciones

Autor: Diego Arévalo Ovalle

Asesor Pedagógico: Óscar Mauricio Salazar

Diseñador Gráfico: Diego Arévalo Ovalle
Asistente: Alejandra Morales

Este material pertenece al Politécnico Grancolombiano.

Por ende, es de uso exclusivo de las Instituciones
adscritas a la Red Ilumno. Prohibida su reproducción
total o parcial.

POLITÉCNICO GRANCOLOMBIANO 18