Ecuaciones de recurrencia

Mónica Marı́a Lozano Romero

Politécnico Grancolombiano
2010
 Índice general

1. Ecuaciones de recurrencia 1
1.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Definiciones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1. Tipos de ecuaciones de recurrencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Ecuaciones de recurrencia lineales y homogéneas . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.1. Ecuaciones de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.2. Ecuaciones de segundo orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Ecuaciones de recurrencia lineales no Homogéneas . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

i
 Ecuaciones de recurrencia

ii
 Capı́tulo 1: Ecuaciones de recurrencia

En este capı́tulo introducimos las métodos matemáticos más comunes para resolver ecuaciones de
recurrencia para estimar complejidades de algoritmos. Adicionalmente, se define y explican los tipos de
ecuaciones de recurrencia más frecuentes en el análisis de algoritmos y los ejemplos más conocidos. El
contenido de éste capı́tulo se basó en gran parte de los autores [2] y [1].

Al final del capı́tulo el estudiante estará en la capacidad de plantear ecuaciones de recurrencia de un

problema propuesto que ası́ lo necesite y establecer si tiene o no solución para que de esa manera pueda
calcular un valor de complejidad del algoritmo o simplemente encontrar una fórmula más sencilla que
resuelva el mismo problema.

Sección 1.1: Introducción

Una ecuación de recurrencia es una expresión finita que define una sucesión, en la cual cada uno de sus
elementos se determina a partir de otros elementos, más sencillos, que incluyen casos iniciales o básicos.
El análisis de algoritmos y las ecuaciones de recurrencia están ı́ntimamente relacionadas, dado que éstas
son una herramienta con la que se puede estimar complejidades de algoritmos, puesto que utiliza funciones
definidas sobre los naturales, que en el caso de un algoritmo recurrente calculan la demanda de recursos a
lo largo de su ejecución.

Uno de los problemas frecuentes con las ecuaciones de recurrencias no es sólo plantearlas sino solu-
cionarlas, dado que solucionar éste tipo de ecuaciones consiste en encontrar una expresión cerrada para
una sucesión que satisfaga la ecuación, es decir, una expresión en la que los valores de los elementos de
la sucesión no dependan de otros valores de la sucesión. Es importante encontrar expresiones cerradas ya
que a a partir de una ecuación recurrente resulta difı́cil establecer órdenes de crecimiento en el tiempo
(complejidad de ejecución) de los recursos que necesita el algoritmo correspondiente.

Solucionar ecuaciones recurrentes en computación es un tema al que no le podemos ser indiferentes,

dado que muchos de los objetos informáticos definidos están definidos de manera recurrente y los razo-
namientos inductivos son la base para los desarrollos teóricos y prácticos de ésta ciencia. Adicionalmente
cabe resaltar que las ideas expuestas en éste capı́tulo son soportadas por la teorı́a clásica de ecuaciones
diferenciales, aunque son teorı́as que se aplican de manera distinta tienen varias similitudes evidentes cuan-
do se tratan de ecuaciones lineales y no lineales ya sean homogéneas o no homogéneas. No obstante hay
ecuaciones diferenciales y recurrentes cuya solución están fuera del alcance de los métodos que aquı́ se
exponen, incluso puede ser imposible encontrar soluciones por métodos algoritmicos.

Sección 1.2: Definiciones básicas

Tal como mencionamos en la introducción del capı́tulo, las ecuaciones o relaciones de recurrencia son
sucesiones que se expresan en términos de elementos anteriores más sencillos. Primero veamos que es una
sucesión, una sucesión es una secuencia de números naturales que de a parejas tienen alguna relación, por

1
Ecuaciones de recurrencia Definiciones básicas

ejemplo:

(2, 4, 8, 16, . . . , 2n, . . .)

es la sucesión creciente de números pares, y si uno toma dos números consecutivos,n y n + 1, de la sucesión
se sabe que al dividirse n + 1 en n nos va a dar como resultado 2. Una sucesión se suele representar como
(an ), donde cada an es un elemento de la sucesión, el ejemplo anterior se puede escribir de forma concisa
como an = 2an−1 (el subı́ndice n de la sucesión habla del elemento que está en la posición n de la misma).
Pero note que esa sucesión puede ser alguna de las siguientes:

(2, 4, 8, . . . , 2n, . . .)
(4, 8, . . . , 2n, . . .)
(100, 200, 400, . . . , 2n, . . .)

para asegurar que realmente la sucesión propuesta representa la sucesión del ejemplo toca definirle condi-
ciones iniciales o condiciones de frontera que diga desde que número inicia la sucesión, de esa manera la
sucesión correcta que modela el ejemplo propuesto es:

an = 2an−1 con a0 = 2.

De esa manera la sucesión tiene un caso base (a0 ) y un caso recurrente (an en términos de an−1 ), otros
ejemplos de ecuaciones de recurrencia son:
an = an−1 + 3 con a0 = 5
an = an−1 + 3an−2 con a0 = 3

1.2.1: Tipos de ecuaciones de recurrencia

Existen distintos tipos de ecuaciones de recurrencia, estos tipos se clasifican por ordenes, para aclarar
que significado una ecuación de orden k, empecemos definiendo que es una ecuación de recurrencia de
primer orden.

Una ecuación de recurrencia de primer orden es una ecuación que define una sucesión cuyo elementos
que no son caso base depende el elemento inmediatamente anterior, tal como ocurre en el ejemplo an = 2an−1 .
Pero si en cambio se tiene una ecuación de recurrencia como an = 2an−1 + 3an−2 es una ecuación de orden
dos, es decir, el orden de una relación de recurrencia es el número de elementos del cuál depende el elemento
n de una sucesión. De esa manera la ecuación:

an = Cn−1 an−1 + Cn−2 an−2 + . . . + Ck an−k

es una relación de recurrencia de orden k. Note que la ecuación anterior se puede reescribir como:

an − Cn−1 an−1 − Cn−2 an−2 − . . . − Ck an−k = 0

Más aún la variable an puede estar acompañada de una constante (en ese caso uno), de esa forma se puede
reescribir de la siguiente manera:

Cn an + Cn−1 an−1 + Cn−2 an−2 + . . . + Ck an−k = 0 (n ≥ k).

2
Ecuaciones de recurrencia Ecuaciones de recurrencia lineales y homogéneas

La anterior ecuación se dice que es una ecuación homogénea (porque es igual a cero), pero si en cambio se
tuviera que fuera igual a algo distinto de cero, por ejemplo un polinomio, se dice entonces que la ecuación
es no homogénea.

Hasta ahora hemos sólo dado ejemplos de ecuaciones de recurrencia que son lineales, dado que ningún
elemento de la ecuación esta elevado a alguna potencia positiva. De hecho, en este capı́tulo sólo estudiaremos
métodos para resolver ecuaciones de recurrencias lineales homogéneas o no homogéneas, puesto que las
que no son lineales necesitan estrategias y teorı́as más avanzadas que se salen del alcance del curso.

Sección 1.3: Ecuaciones de recurrencia lineales y homogéneas

En esta sección sólo nos concentramos en mostrar las “recetas” para solucionar ecuaciones lineales
homogéneas.

1.3.1: Ecuaciones de primer orden

Para empezar estudiemos el caso particular de la ecuaciones de primer orden, ası́ que considere la
sucesión an = 3an−1 con a0 = 5. Observemos si calculamos los primeros 6 elementos de la sucesión:

a0 = 5
a1 = 3 ⋅ a0 = 3(5)
a2 = 3 ⋅ a1 = 3(3 ⋅ 5) = 32 (5)
a3 = 3 ⋅ a2 = 3(32 5) = 33 (5)
a4 = 3 ⋅ a3 = 34 (5)
a5 = 3 ⋅ a4 = 35 (5)
De esto podemos deducir que el valor de a20 = 5(320 ) y en general que an = 5(3n ), esta es la fórmula
cerrada de la ecuación de recurrencia an = 3an−1 con a0 = 5.

En general cuando se tiene una ecuación de recurrencia de primer orden ésta tiene la forma an = dan−1
y d una constante, y una condición inicial a0 = A, la formúla cerrada para este tipo de ecuaciones es
sencillamente an = A ⋅ dn . Cabe resaltar que no todas las ecuaciones de recurrencia de primer orden son de
esa manera, el siguiente ejemplo ilustra lo que se está diciendo:

Ejemplo 1.1
Tal vez algoritmo más popular para ordenar un conjunto de número es el método de ordenación burbuja,
la entrada es un arreglo A[n] de números que se desean ordenar de menor a mayor, la idea de fondo de
este algoritmo es comparar cada uno de los números con todos los demás que están en el arreglo e irlo
moviendo siempre y cuando encuentre un número menor que el en una posición anterior en el arreglo:
Para determinar la ecuación de complejidad de este algoritmo, contamos el número de operaciones que
ejecuta para realizarse, sea an la sucesión que representa el número de operaciones que el algoritmo realiza
para ordenar los n números del arreglo A, de esa manera obtenemos que:
an = an−1 + n − 1 con n ≥ 2 y a1 = 0.
Esto surge de la siguiente manera, dada la lista de n números, se hacen en el peor de los casos n − 1
comparaciones para mover el número más pequeño de la lista a la primera posición de la lista, y para los

3
Ecuaciones de recurrencia Ecuaciones de recurrencia lineales y homogéneas

Algoritmo 1.1 Ordenación burbuja

for i = 1 to n − 1 do
for j = n to i + 1 do
if A[j] < A[j − 1] then
temp = A[j − 1]]
A[j − 1] = A[j]
A[j] = temp
end if
j =j−1
end for
end for

n − 1 números restantes por ordenar requieren an−1 comparaciones para ordenarse completamente (pues en
el proceso el primer número se repite para todos los demás números de la lista).

Note que el sumando n − 1 hace que la ecuación de la recurrencia no sea homogénea. Dado que aún no
tenemos los métodos para resolver relaciones de recurrencia no homogéneas, veamos a ver si encontramos
un patrón, para esto calculemos distintos valores de la sucesión:

a1 = 0
a2 = 1 + 2 − 1 = 1
a3 = 1 + 3 − 1 = 1 + 2
a4 = 1 + 2 + 4 − 1 = 1 + 2 + 3
a5 = 1 + 2 + 3 + 5 − 1 = 1 + 2 + 3 + 4

El patrón que podemos identificar es que an = 1 + 2 + 3 + . . . + n del cuál sabemos cual es su resultado (De
un ejercicio del capı́tulo anterior), entonces an = n(n+1)
2 . ◻

Hasta ahora hemos visto dos aproximaciones para encontrar la solución de relaciones de recurrencia
de primer orden,como:

a) Las sucesiones de la forma an = dan−1 con n ≥ 0 y a0 = A.

b) Las sucesiones de la forma an = an−1 + α, donde α puede ser como en el caso del Ejemplo 1.1 (un
polinomio) o una constante, para este tipo de ecuaciones las resolvemos -por ahora- buscando un
patrón de los elementos de la sucesión.

1.3.2: Ecuaciones de segundo orden

Ahora, continuaremos con buscar la manera de solucionar ecuaciones de recurrencia de segundo orden
y de orden k. Primero recordemos que la ecuación de recurrencia lineal de orden k con k ∈ N, Ci ≠ 0 y (an )
una sucesión, puede ser de la siguiente manera:

Cn an + Cn−1 an−1 + Cn−2 an−2 + . . . + Ck an−k = f (n) (n ≥ k)

Si f (n) = 0 se dice que la ecuación es homogénea, si f (n) ≠ 0 es no homogénea, de esa manera una de orden
dos homogénea serı́a Cn an + Cn−1 an−1 + Cn−2 an−2 = 0 (n ≥ 2). Basados en lo que vimos con anterioridad para

4
Ecuaciones de recurrencia Ecuaciones de recurrencia lineales y homogéneas

este tipo de ecuaciones queremos una solución de la forma an = c ⋅ rn con c, r ∈ N.

Si sustituimos en la an = c ⋅ rn en la ecuación se tendrı́a:

Cn ⋅ c ⋅ rn + Cn−1 ⋅ c ⋅ rn−1 + Cn−2 ⋅ c ⋅ rn−2 = 0
Con alguna manipulación algebraica la fórmula anterior se puede reescribir como: c ⋅ rn−2 (Cn ⋅ r2 + Cn−1 ⋅ r +
Cn−2 ) = 0, y cancelando se obtiene:
Cn ⋅ r2 + Cn−1 ⋅ r + Cn−2 = 0
este es el polinomio caracterı́stico de grado 2, y los valores que lo satisfacen se conocen como raı́ces, como
es de grado dos entonces tiene dos raı́ces, llamélas r1 , r2 . Pero éstas raı́ces pueden ser de tres maneras
distintas:
a) Ambas son reales y distintas.

b) Ambas son reales e iguales (es decir, de multiplicidad dos).

c) Son ambas complejas

Cada uno de los casos los ilustraremos con ejemplos y luego los resumimos en teoremas de tal manera que
sea la “receta” para solucionar ecuaciones de recurrencia de este tipo, adicionalmente al final de la sección
se generaliza las soluciones para una ecuación de recurrencia de orden k.

Raı́ces reales y distintas

Para el primer caso, se tiene el siguiente ejemplo:

Ejemplo 1.2
Resolvamos la relación de recurrencia an + an−1 − 6an−2 = 0 con n ≥ 2 y con condiciones iniciales: a0 = 1 y
a1 = 2. Sı́ an = c ⋅ rn es solución entonces se tiene:

an + an−1 − 6an−2 = 0
⇒ c ⋅ rn + c ⋅ rn−1 − 6c ⋅ rn−2 = 0
⇒ c ⋅ rn−2 (r2 + r − 6) = 0
⇒ r2 + r − 6 = 0
⇒ (r + 3)(r − 2) = 0
De esa manera r1 = −3 y r2 = 2, es decir, son reales y distintas. Por lo tanto an = c1 ⋅ (−3)n y an =
c2 ⋅ (2n ) son soluciones de la ecuación de recurrencia, note que son linealmente independientes entonces
una combinación lineal de ellas también es solución. Como sabemos que son linealmente independientes?,
porque primero ninguna es múltiplo de la otra y segundo si para k1 , k2 ∈ R se cumple k1 ⋅ 2n + k2 ⋅ (−3)n = 0
para todo n ∈ N , entonces k1 = k2 = 0 (esto se cumple por la primera razón, puede demostrarlo como
ejercicio si lo desea). De esa manera la solución general de la ecuación es:
an = c1 ⋅ (−3)n + c2 ⋅ (2n )
Sólo nos hace falta encontrar los valores de c1 y c2 , para eso usamos las condiciones iniciales a0 y a1 ,
entonces se tiene que:

5
 Ecuaciones de recurrencia Ecuaciones de recurrencia lineales y homogéneas

a0 = 1 = c1 ⋅ (−3)0 + c2 ⋅ (20 ) = c1 + c2
a1 = 2 = c1 ⋅ (−3)1 + c2 ⋅ (21 ) = −3c1 + 2c2

Al resolver el sistema se obtiene que c1 = 0 y c2 = 1, de esa manera las solución final es:
an = 2n .
◻

Raı́ces reales e iguales

Las raı́ces de un polinomio caracterı́stico de grado dos pueden ser iguales y la manera de encontrar la
solución de una ecuación de recurrencia de segundo orden funciona ligeramente distinto a como vimos en
la subsección anterior. Para este caso considere el siguiente ejemplo:

Ejemplo 1.3
Resolvamos la ecuación de recurrencia an+2 = 4an+1 − 4an con n ≥ 0 y a0 = 1, a3 = 1. Como en el ejemplo
anterior la solución es de la forma an = c ⋅ rn , reemplazando y simplificando obtenemos el polinomio carac-
terı́stico r2 − 4r + 4 = 0 del cual se obtienen sus dos raı́ces son r = 2 (es decir, r tiene multiplicidad dos).
Entonces tiene por solución an = c1 ⋅ 2n y an = c2 ⋅ 2n , pero a diferencia del ejemplo anterior la soluciones
no son linealmente independientes. De esa manera toca buscar otra solución que sea linealmente de la otra
pero que utilice la raı́z encontrada, usemos por ejemplo an = n ⋅ 2n , ahora demostremos que es una solución
de la ecuación de recurrencia:

an+2 = 4an+1 − 4an

(n + 2)(2n+2 ) = 4(n + 1)2n+2 − 4n2n
(n + 2)(2n+2 ) = 2(n + 1)2n+2 − n2n+2
(n + 2)(2n+2 ) = (2n + 2 − n)2n+2
(n + 2)(2n+2 ) = (n + 2)2n+2
La última igualdad claramente es cierta, entonces an = n⋅2n sı́ es solución de la ecuación y es linealmente
independiente de an = c1 ⋅ 2n , de esa manera la solución general es (recuerde que cualquier múltiplo de una
solución también es solución):
an = c1 ⋅ 2n + c2 ⋅ n ⋅ 2n
Con las condiciones iniciales encontramos que c1 = 1 y c2 = 21 , ası́ la solución final es:
an = 2n + 21 ⋅ n ⋅ 2n = 2n + n ⋅ 2n−1 (n ≥ 0)
◻

Raı́ces complejas
El último caso, es que las raı́ces del polinomio caracterı́stico son números complejos. En este caso es
muy importante recordar el Teorema de Moivre sobre los números complejos:

Teorema 1.1
(cos(θ) + i sin(θ))n = cos(n ⋅ θ) + i sin(n ⋅ θ) (n ≥ 0)
◇

6
Ecuaciones de recurrencia Ecuaciones de recurrencia lineales y homogéneas

Adicionalmente recordemos que un número complejo es un punto en el plano cartesiano que se representa
comúnmente como z = x + iy, √ pero también se puede representar en términos de cosenos y senos: z =
r(cos(θ) + i sin(θ)) donde r = x + y y θ = tan ( x ) para x ≠ 0 (cuando x = 0, claramente θ es o π2 o 3π
2 2 −1 y
2 ).
De esa manera se tiene que:
z n = rn ⋅ (cos(n ⋅ θ) + i sin(n ⋅ θ) (n ≥ 0))
Ahora sı́, demos un ejemplo de como resolver ecuaciones de recurrencia con raı́ces complejas:

Ejemplo 1.4
Resolvamos al ecuación de recurrencia an = 2(an−1 − an−2 ) con n ≥ 2 y a0 = 1, a1 = 2. De la misma manera
como se ha hecho en los ejemplos anteriores an = c ⋅ rn es solución, por lo que obtenemos el polinomio
caracterı́stico r2 − 2r + 2 = 0 cuyas raı́ces son 1 + i y 1 − i, es decir, raı́ces complejas. Por lo tanto las
soluciones del ecuación son an = c1 ⋅ (1 + i)n y an = c2 ⋅ (1 − i)n y como son linealmente independientes (por
que?) entonces la solución general es:
an = c1 ⋅ (1 − i)n + c2 ⋅ (1 + i)n
Pero ahora necesitamos calcular cuanto es (i + 1)n y (1 − i)n , para esto utilizamos el teorema de Moivre y
la definición de número complejo:
√ √
(i + 1)n = [(√2)(cos( π4 ) + i sin π4 )]n = (√2)n (cos( nπ 4 ) + i sin 4 )
nπ

(1 − i)n = [( 2)(cos( π4 ) − i sin π4 )]n = ( 2)n (cos( nπ 4 ) − i sin 4 )

nπ

Entonces, la formúla general queda:

√ √
an = c1√⋅ ( 2)n (cos( nπ 4 ) + i sin nπ
4 ) + c 2 ⋅ ( 2)n (cos( nπ
4 ) + i sin 4 )
nπ

an = (√2)n ((c1 + c2 ) cos( 4 ) + (c1 − c2 )i sin 4 )

nπ nπ

an = ( 2)n (k1 cos( nπ 4 ) + k2 sin 4 )

nπ

Con k1 = c1 + c2 y k2 = (c1 − c2 )i, utilizando las condiciones iniciales y reemplanzodolas en la formúla

encontramos que k1 = 1 y que k2 = 1, de esa manera la solución final es:
√
an = ( 2)n (cos( nπ
4 ) + sin 4 ).
nπ

Ya terminamos de ver los tres distintos tipos de maneras en que las raı́ces del polinomio caracterı́stico
de una ecuación de orden dos pueden usarse para encontrar la solución de ésta. Todo lo que hemos explicado
se puede extender de forma general para cualquier ecuación de recurrencia de orden k, dado que en todos
los ejemplos lo que realmente se soluciona es el polinomio caracterı́stico de la relación de recurrencia
involucrada y a partir de sus raı́ces se propone la solución general de la ecuación , aunque también hay
que resaltar que hay que tener en cuenta si las raı́ces son linealmente independientes o no y de acuerdo a
eso acomodar la solución para que se puedan encontrar la combinación lineal que solucione la ecuación, ya
lo demás son manipulaciones algebraicas que junto con las condiciones de frontera permiten encontrar la
solución final. A continuación resumimos los pasos de como solucionar una ecuación de recurrencia:

Teorema 1.2
Dada una ecuación de recurrencia an de orden k con condiciones iniciales establecidas, los siguientes pasos
se realizan para encontrar la fórmula cerrada que la soluciona:

7
Ecuaciones de recurrencia Ecuaciones de recurrencia lineales no Homogéneas

a) Se encuentra el polinomio caracterı́stico con la solución an = c ⋅ rn .

b) Se encuentran las raı́ces del polinomio, se verifica que las raı́ces son todas reales y distintas, o si
algunas de ellas tienen una multiplicidad positiva o si son complejas (note que es posible que den
todos los casos al mismo tiempo, de esa manera hay que combinar las estrategias planteadas en los
ejemplos dados).
c) Se verifican que las soluciones sean linealmente independientes, de no hacerlo hay que volverlas
linealmente independientes para poder plantear la combinación lineal an = c1 s1 + c2 s2 + . . . + ck sk ,
donde ci ∈ R y sk una solución de la ecuación.
d) Se consideran las condiciones iniciales y se encuentran los valores de las constantes ci de la solución
general.
e) Se manipula algebraicamente para encontrar la solución final de la ecuación.
◇

Sección 1.4: Ecuaciones de recurrencia lineales no Homogéneas

En esta sección vamos a explicar como resolver ecuaciones de recurrencia no homogéneas, recordemos
de la sección anterior que es una ecuación de recurrencia lineal de orden k no homogénea con k ∈ N, Ci ≠ 0
y (an ) una sucesión:
Cn an + Cn−1 an−1 + Cn−2 an−2 + . . . + Ck an−k = f (n) (n ≥ k)
f (n) es cualquier cosa distinta de cero, ya sea una constante o un polinomio. Hay que resaltar que no todas
las ecuaciones no homogéneas se pueden resolver, razón por la cuál vamos a ver métodos de acuerdo a la
forma de f (n).

Como primera aproximación uno puede por sustitución encontrar una fórmula para todos los f (i)′ s,
pero ésta aproximación es práctica en ecuaciones de recurrencias de primer orden, por ejemplo considere
la ecuación de recurrencia an − an−1 = f (n), si listamos algunos de sus elementos tendremos:

a1 = a0 + f (1)
a2 = a1 + f (2) = a0 + f (1) + f (2)
a3 = a2 + f (n) = a0 + f (1) + f (2) + f (3)
.
.
.
an = an−1 + f (n) = a0 + f (1) + f (2) + f (3) + . . . + f (n) = a0 + (∑ i ∣ 1 ≤ i ≤ n ∶ f (i))
Si se conoce a que converge (∑ i ∣ 1 ≤ i ≤ n ∶ f (i)), se puede entonces resolver la ecuación de recurrencia,
de lo contrario toca utilizar algún otro método.

La solución de las ecuaciones lineales no homogéneas de orden k difiere de las soluciones de las ecua-
ciones homogéneas en que tiene una solución particular, dicha solución va a depender completamente de

8
Ecuaciones de recurrencia Ecuaciones de recurrencia lineales no Homogéneas

f (n). De esa manera si se desea solucionar una ecuación de recurrencia an , la solución general es de la
manera:

an = (an )h + (an )p

Donde (an )h es la solución a la ecuación homogénea del problema y (an )p es la solución particular de
la ecuación de acuerdo a f (n). Ası́ que en estos casos el trabajo es doble, primero hay que encontrar la
solución de la versión homogénea del problema y luego basándonos en lo que es f (n) encontrar la parti-
cular. Sin embargo, hay que tener cuidado cuando se escoge la solución particular dado que esta debe ser
linealmente independiente de la solución homogénea.

A continuación se enuncian los teoremas que nos indican como resolver ecuaciones lineales no ho-
mogéneas de primer y segundo orden cuando f (n) = k ⋅ rn :

Teorema 1.3
Considere la ecuación de recurrencia lineal de primer orden:

Cn an + Cn−1 an−1 = k ⋅ rn

Donde k es una constante y n ≥ 1, para este tipo de ecuaciones puede ocurrir al menos uno de los siguientes
casos:

1. Si an = c ⋅ rn no es una solución a la ecuación homogénea asociada Cn an + Cn−1 an−1 = 0 entonces

(an )p = c ⋅ rn con c una constante.

2. Si an = c ⋅ rn es una solución a la ecuación homogénea asociada Cn an + Cn−1 an−1 = 0 entonces (an )p =

b ⋅ n ⋅ rn con b una constante, dado que hay que asegurar que ambas soluciones son linealmente
independientes.

Teorema 1.4
Considere la ecuación de recurrencia lineal de segundo orden:

Cn an + Cn−1 an−1 + Cn−2 an−2 = k ⋅ rn

Donde k es una constante y n ≥ 2, para este tipo de ecuaciones puede ocurrir al menos uno de los siguientes
casos:

a) (an )p = c ⋅ rn , si dicha solución no está en (an )h (es decir, que no aparece en ninguno de los sumandos
de la solución homogénea de la ecuación de recurrencia homogénea asociada).

b) (an )p = b ⋅ n ⋅ rn , si an = c ⋅ rn aparece en la solución de (an )h .

c) (an )p = c ⋅ n2 ⋅ rn , si (an )p = bn ⋅ rn aparece en la solución de (an )h .

9
Ecuaciones de recurrencia Ecuaciones de recurrencia lineales no Homogéneas

Note que en ambos teoremas se tiene en cuenta la solución del la ecuación homogénea asociada para ase-
gurar la independencia lineal. Ahora nos preguntamos como solucionar una ecuación de recurrencia lineal
no homogénea cuyo orden es mayor a dos?; bueno para esto toca revisar los elementos que conforman f (n)
y combinar las distintas soluciones propuestas en la Tabla 1.1. A continuación se explica en detalle como
solucionar una ecuación lineal no homogénea de orden k.

Considere la siguiente ecuación de recurrencia con coeficientes constantes: Cn an + Cn−1 an−1 + Cn−2 an−2 +
. . . + Ck an−k = f (n) donde Cn , Cn−k ≠ 0 y sea (an )h la parte homogénea de la solución an :

a) Si f (n) es múltiplo de alguna de las constantes de la primera columna de la Tabla 1.1 y no es solu-
ción de (an )h , entonces (an )p tiene la forma que se muestra en la segunda columna de la Tabla. (Las
constantes mencionadas en la segunda columna puede ser obtenidas reemplazando en la solución pro-
puesta las condiciones iniciales involucradas en la ecuación de recurrencia que se está solucionando).

b) Cuando f (n) es una suma de múltiplos constantes de los términos como los de la primera columna de
la Tabla 1.1 y ninguno de esos términos es solución de (an )h , entonces (an )p es la suma de los términos
correspondientes en la segunda columna de la Tabla 1.1. Por ejemplo, si f (n) = n2 +4 sin(3n) y ninguno
de los sumandos de f (n) aparece en (an )h entonces (an )p = (A2 n2 +A1 n+A0 )+(A sin(2n)+B cos(2n)).

c) Ahora, si algún sumando de f (n),llamémoslo fi (n), es un múltiplo constante de una solución de

(an )h , toca multiplicar la solución particular (ani )p correspondiente a fi (n) por la mı́nima potencia
de n, ns , para que ningún sumando de ns fi (n) sea una solución de (an )h , de esa manera ns (ani )p es
la parte correspondiente de (an )p .

Cuadro 1.1: Forma de f (n) vs la solución (an )p

f (n) (an )p
c constante A, constante
n A1 n + A0
n 2 A2 n2 + A1 n + A0
nt , t ∈ Z+ At nt + At−1 nt−1 + . . . + A1 n + A0
r , r∈R
n Arn
sin(αn) A sin(αn) + B cos(αn)
cos(αn) A sin(αn) + B cos(αn)
t
nr n r (At nt + At−1 nt−1 + . . . + A1 n + A0 )
n

rn sin(αn) rn (A sin(αn) + B cos(αn))

n
r cos(αn) rn (A sin(αn) + B cos(αn))

El siguiente ejemplo se ilustra el método explicado:

Ejemplo 1.5
Considere la relación de recurrencia no homogénea an+2 − 10an+1 + 21an = f (n) con n ≥ 0. La solución de la
ecuación homogénea asociada es (porque?):

(an )h = c1 (3n ) + c2 (7n )

10
 Ecuaciones de recurrencia Ejercicios

para las constantes arbitrarias c1 , c2 .

En la Tabla 1.2 se muestran las soluciones particulares de la ecuación de acuerdo a posibles definiciones
de f (n). De la Tabla 1.2 podemos ver que en las últimas tres filas uno de los sumandos de f (n) aparece

Cuadro 1.2: Posibles valores de f (n) del Ejemplo 1.5

f (n) (an )p
5 A0
3n2 − 2 A3 n2 + A2 n + A1
7(11n ) A4 (11n )
31rn , r ≠ 3, 7 A5 (rn )
6(3n ) A6 n(3n )
2(3n ) − 8(9n ) A7 n(3n ) + A8 (9n )
4(3n ) − 7(7n ) A9 n(3n ) + A9 n(7n )

en la solución de (an )h , razón por la cual el sumando que aparece en la solución homogénea en la solución
particular se multiplica por n (pues es la mı́nima potencia de n que no está en la solución homogénea) la
solución propuesta en la Tabla 1.1, pero si n apareciera en alguno de los sumandos de la solución homogénea
entonces tocarı́a multiplicar la solución particular del sumando involucrado por n2 . ◻

Sección 1.5: Ejercicios

1. Encuentre la ecuación de recurrencia de las siguientes series numéricas

a) 2,10,50,250,. . .
b) 1, 1/3, 1/9, 1/27. . .
c) 6, -18, 54, -162,. . .
d) 7, 14/5,28/25, 56/125, . . .

2. Encuentre la solución general de las siguientes relaciones de recurrencia:

a) an+1 − 1,5an = 0, n ≥ 0.
b) 3an+1 − 4an = 0, n ≥ 0 y a1 = 5.
c) 2an − 3an−1 = 0, n ≥ 1 y a4 = 81.
d) 4an − 4an−1 = 0, n ≥ 1.

3. Si an ,n ≥ 0, es una solución de la relación de recurrencia an+1 − can = 0 y a3 = 153/49, a5 =

1377/2401,cuál es el valor de c?.

11
Ecuaciones de recurrencia Ejercicios

4. El número de bacterias de un cultivo es 1000 (aproximadamente) y esa cantidad se incrementa un

250 por 100 cada 2 horas. Defina una relación de recurrencia y encuentre la solución respectiva para
determinar el número de bacterias presentes después de un dı́a.

5. Si Laura invierte 100 dólares al 6 por ciento de interés compuesto trimestral. Cuántos meses debe
esperar para obtener el doble de lo que invirtió?. NOTA: Laura no puede retirar el dinero antes de
terminar el trimestre.

6. Carlos invirtió las ganancias de las acciones que recibió hace 15 años en una cuenta que pagaba el
ocho por ciento de interés compuesto al trimestre. Si ahora su cuenta tiene 7218.27 dólares, cuál fue
su inversión inicial?.

7. Encuentre el valor de a10 si a3n = 7a3n−1 , n ≥ 1, a0 = 3.

8. Encuentre el valor de an , n ≥ 2, si 5nan + 2nan−1 = 2an−1 , n ≥ 3 y a3 = −30.

9. Demuestre que la definición inductiva o ecuación de recurrencia de los números de fibonacci Fn+2 =
Fn+1 + Fn , n ≥ 0, F0 = 0, F1 = 1 tiene como solución:
√ n √ n
1 1+ 5 1− 5
Fn = √ [( ) −( ) ]
5 2 2

10. Resuelva la ecuación de recurrencia an = 2(an−1 − an−2 ), n ≥ 2, a0 = 1, a1 = 2.

11. Encuentre la ecuación de recurrencia para le número de sucesiones binarias de longitud n que no
tienen ceros consecutivos.

12. Resuelva la siguiente relación de recurrencia 2an+3 = an+2 + 2an+1 − an , n ≥ 0, a0 = 0, a1 = 1, a2 = 2.

13. Resuelva la siguiente ecuación de recurrencia an+2 = 4an+1 − 4an , n ≥ 0, a0 = 1, a1 = 3.

14. Resuélvanse las siguiente ecuaciones de recurrencia:

a) an = 5an−1 + 6an−2 , n ≥ 2, a0 = 1, a1 = 3.
b) 2an+2 − 11an+1 + 5an = 0, n ≥ 0, a0 = 2, a1 = −8.
c) 3an+1 = −2an + an−1 = 0, n ≥ 1, a0 = 7, a1 = −3.
d) an+2 + an = 0, n ≥ 0, a0 = 0, a1 = 3.
e) an+2 + 4an = 0, n ≥ 0, a0 = a1 = 1.
f) an − 6an−1 + 9an−2 = 0, n ≥ 2, a0 = 5, a1 = 12.
g) an + 2an−1 + 2an−2 = 0, n ≥ 2, a0 = 1, a1 = 3.
h) an = 7an−1 − 10an−2 , n ≥ 2, a0 = 3, a1 = 15.
i) 9an+2 + 12an+1 + 4an = 0, n ≥ 0, a0 = 1, a1 = 4.
j) an = 3an−2 + 2an−3 , n ≥ 3, a0 = 1, a1 = 3, a2 = 7.

15. Si a0 = 0, a1 = 1, a2 = 4, a3 = 37 cumplen la relación de recurrencia an+2 + ban+1 + can = 0, n ≥ 0. Donde

b y c son constantes, encuentrése a solución de an .

12
Ecuaciones de recurrencia Ejercicios

16. Encuentre y resuelva la relación de recurrencia para encontrar el número de formas de estacionar
motocicletas y automóviles en una fila de n espacios, si cada motocicleta necesita un espacio, mien-
tras que una automóvil necesita dos (en aparencia las motocicletas son iguales a los automóviles y
viceversa, y se quieren ocupar los n espacios).

17. Usando la solución de la ecuación de recurrencia de los números de fibonnaci demuestre que:
√
Fn+1 1 + 5
lı́m =
n→∞ Fn 2
Este lı́mite se conoce como la razón dorada.

18. Encuentre y resuelva la ecuación de recurrencia que permite contar el número de sucesiones ternarias
(0, 1, 2) de n dı́gitos, sin ningún par de ceros consecutivos.

19. Encuentre y resuelva la ecuación de recurrencia que permite contar el número de formas de aplicar
n fichas rojas, blancas, verdes,azules, de modo que no haya fichas azules consecutivas.

20. Resuelva la ecuación de recurrencia a2n+2 − 5a2n+1 + 4a2n = 0, n ≥ 0,a0 = 4,a1 = 13.

21. Determinese las constantes b y c si an = c1 + c2 (7n ), n ≥ 0, es la solución general de la relación

an+2 + ban+1 + can = 0, n ≥ 0.

22. Paula pidió un préstamo de S cantidad de diner a pagar en T plazos. Si i es el interés del préstamo
por plazo, qué pago (constante) P debe realizar al final de cada plazo?.

23. Para n ≥ 1, sea C un conjunto que contiene 2n números reales. Cuántas comparaciones deben efec-
tuarse entre pares de números de C para determinar los elementos máximo y mı́nimo de C?.

24. Los registros ambientales muestran que en cierto lago la población de una especie especı́fica de corales
aumenta en una tasa triple que la del año anterior. Se comienzan con 5000 corales y al año siguiente
hay 5500; se retiran 200 del lago para incrementar el número en otros lagos. Al seguir quitando 200
corales al final de cada año, si an representa la población de caracoles en el lago original después de
n años, hállese y resuélvase la relación de recurrencia para an , n ≥ 0.

25. Resuelva las siguientes ecuaciones de recurrencia:

a) an+1 − an = 2n + 3, n ≥ 0, a0 = 1.
b) an+1 − an = 3n2 − n, n ≥ 0, a0 = 3.
c) an+1 − 2an = 5, n ≥ 0, a0 = 1.
d) an+1 − 2an = 2n , n ≥ 0, a0 = 1.

26. Encuentre una ecuación de recurrencia para deducir la formúla de Σni=0 i2 .

27. a) Sean n rectas trazadas en el plano de manera que cada recta corte a las restantes, pero que
no hayan tres coincidentes. Para n ≥ 0, sea an la cuenta del número de regines en que n rectas
dividen el plano. Encuentre y resuelva la relación de recurrencia para an .
b) Para la situación del apartado a), sea bn la cuenta del número de regiones infinitas resultante,
encuentre y resuelva la relación de recurrencia de bn .

13
Ecuaciones de recurrencia Ejercicios

28. El primero de enero, Pedro deposita 1000 dólares en una cuenta que paga el seis porciento de interés
compuesto mensual. Todos los primeros del mes, ingresa 200 dólares a su cuenta. Si hace lo mismo
durante cuatro años siguientes, cuánto dinero habrá en su centa exactamente cuatro años después de
abrirla?.

29. Resuelva la siguiente ecuación de recurrencia an+2 − 6an+1 + 9an = 3(2n ) + 7(3n ), n ≥ 0, a0 = 1, a1 = 4.

30. La solución general de la relación de recurrencia an+2 + b1 an+1 + b2 an = b3 n + b4 , n ≥ 0, bi constante,

1 ≤ i ≤ 4, es c1 2n + c2 3n + n − 7, halle los valores bi ,1 ≤ i ≤ 4.

31. Determine el número de sucesiones cuaternarias (0, 1, 2, 3) de n dı́gitos , donde nunca haya un 3 a la
derecha de un cero.

32. Resuelva las siguientes ecuaciones de recurrencia:

a) a2n+2 − 5a2n+1 + 6a2n = 7n.

b) an + nan−1 = n!, n ≥ 1, a0 = 1.
c) a2n − 2an−1 = 0, n ≥ 1, a0 = 2. Sugerencia: Tome como bn = log2 an , n ≥ 0.

14
 Bibliografı́a

[1] Ralph P. Grimaldi. Matemáticas discretas y combinatoria. Addison-Wesley Iberoamericana, 1997.

[2] David Gries y Fred B. Schneider. A logical approach to discrete Math. Springer, 1994.

15