Matemática Discreta 1 - Curso 2020,

Resumen de sucesiones definidas por recurrencia

basado en clases 11 (13/05) y 12 (15/05)
El tema correspondiente a esta semana de clase es el de sucesiones
(an )n≥0 definidas a partir de una recurrencia lineal y puede estudiarse en las
secciones 10.1 - 10.4 del Grimaldi. Solamente nos vamos a enfocar en el caso
de recurrencia lineal de primer y segundo orden con coeficientes constantes.
El práctico correspondiente a este tema es el práctico 6.

Una recurrencia lineal de primer orden es de la forma:

Aan + Ban−1 = f (n), ∀n ≥ 1, (1)

donde A, B ∈ R con AB 6= 0 y f : N → R es una función fija.

Una recurrencia lineal de segundo orden es de la forma:

Aan + Ban−1 + Can−2 = f (n), ∀n ≥ 2, (2)

donde A, B, C ∈ R con AC 6= 0 y f : N → R es una función fija.

Si bien se define de forma análoga recurrencias lineales de orden supe-

rior en este curso nos vamos a concentrar exclusivamente en estos dos casos.
Cuando f ≡ 0 decimos que la recurrencia lineal es homogenea. Los otros
casos de funciones que vamos a considerar en el curso son cuando f (n) es un
polinomio, una función exponencial (es decir, f (n) = Arn donde A, r ∈ R)
o suma y producto de estas1 . La razón de esta restricción es que en estos
casos es posible encontrar una expresión explı́cita para an .

También pueden aparecer otras recurrencias lineales que aunque los co-
eficientes no sean constantes sean simples de resolver tales como an = nan−1
para n ≥ 1, o por ejemplo algunos casos en que pueden aplicarse cambio de
variable como por ejemplo an = 2nan−1 + 3n(n − 1)an−2 para n ≥ 2 (con
el cambio de variable an = n!bn y dividiendo luego todo entre n! nos queda
bn = 2bn−1 + 3bn−2 que es homogenea de segundo orden). No hay que asus-
tarse, en los casos en el que el cambio de variable no sea evidente siempre
vamos a decirles el cambio de variable o al menos darles alguna pista.

1
No vamos a considerar el caso trigonométrico que aparece en el Grimaldi.

1
 Luego de haber estudiado esta parte del programa se espera que el estu-
diante sea capaz de:

1. Resolver recurrencias lineales homogeneas de primer y segundo orden

con coeficientes constantes (obtener la solución general y determinar
una solución que verifique ciertas condiciones iniciales).
Ejercicios 1,2,3 del Práctico 6.

2. Resolver recurrencias lineales no homogeneas de primer y segundo or-

den con coeficientes constantes (obtención de una solución particular
y luego la solución general a partir de esta, también determinar una
solución que verifique ciertas condiciones iniciales).
Ejercicios 4,5,6 del Práctico 6.

3. Utilizar cambio de variables para transformar ciertas recurrencia lineal

con coeficientes no constantes en una con coeficientes constantes.
Ejercicios 2,10,15 del Práctico 6.

4. Utilizar el principio de superposición para la obtención de una solución

particular.
Ejercicio 6c. del Práctico 6.

5. Utilizar funciones generatrices para resolver una recurrencia lineal y

también un sistema de recurrencia.
Ejercicios 8,9,10 del Práctico 6.

6. Utilizar ecuaciones de recurrencia para resolver problemas de conteo

y combinatoria.
Ejercicios 7,11,13 del Práctico 6.

Obs: la referencia a los ejercicios es con respecto al práctico 6 del primer semestre de 2020.

2
Resumen de los temas con ejemplos resueltos
0.1. Relaciones en recurrencia lineal homogenea
Sea k ∈ Z+ y c0 , c1 , . . . , ck ∈ R con c0 ck 6= 0. Una relación de la forma
c0 an + c1 an−1 + · · · + ck an−k = f (n), ∀n ≥ k (3)
se llama recurrencia lineal2 de orden k. Observar que las ecuaciones (1) y
(2) son casos particulares con k = 1 y k = 2 respectivamente.

Dada una relación de recurrencia lineal de orden k existen infinitas so-

luciones (an )n≥0 que la verifica. Si despejamos an en la ecuación (3) vemos
que cada término queda determinado conociendo los k términos anteriores.
En particular si fijamos los valores de a0 , a1 , . . . , ak (condiciones iniciales)
entonces queda determinada una única solución.

Cuando f ≡ 0 entonces la ecuación toma la forma:

c0 an + c1 an−1 + · · · + ck an−k = 0, ∀n ≥ k (4)
donde c0 6= 0 y ck 6= 0. En este caso decimos que la relación de recurrencia
es homogenea lineal de orden k.

El conjunto de todas las sucesiones (an )n≥0 que verifican una relación
de recurrencia (4) resulta un espacio vectorial de dimensión k (con la suma
y producto por escalar usuales de las sucesiones). Esto significa que si con-
seguimos obtener k sucesiones linealmente independientes que verifican (4)
entonces cualquier solución va a ser combinación lineal de estas (los coefi-
cientes quedarán determinados por las condiciones iniciales).

Cada relación de recurrencia homogenea (4) tiene asociado un polinomio

(llamado polinomio caracterı́sitico3 ): p(λ) = c0 λk + c1 λk−1 + · · · + ck . La
importancia de este polinomio radica en el hecho de que si λ0 es una raiz
de p(λ) entonces la sucesión an = λn0 verifica (4). En particular si p(λ) tiene
k = gr(p(x)) raices distintas λ1 , λ2 , . . . , λk entonces la solución general viene
dada por an = α1 λn1 +α2 λn2 +· · ·+αk λnk donde los αi son constantes (reales o
complejos). Si tenemos condiciones iniciales a0 , a1 , . . . , ak−1 podemos hallar
los αi resolviendo un sistema.
2
Importante: Hay un error en el libro de Grimaldi al inicio de la sección 10.2, los
coeficientes ci de la recurrencia son constantes, o sea no dependen de n.
3
Una forma simple de obtener el polinomio caracterı́stico es sustituyendo an = λn en
(4) y dividir entre la mayor potencia de λ posible.

3
0.2. Recurrencia lineal homogenea de primer orden
Tenemos una relación del tipo c0 an + c1 an−1 = 0 con polinomio ca-
racterı́stico c0 λ + c1 cuya raiz es r = −c
c0 . Entonces la solución general es
1

cn = αrn , cuando n = 0 obtenemos c0 = α asi que podemos escribir la solu-

ción general como cn = c0 rn de forma que conociendo c0 (condición inicial)
podemos determinar la sucesión. Una sucesión que verifica una recurrencia
lineal homogenea de primer orden se llama progesión geométrica.

Ejemplo 1. Determine (an ) si an = 3an−1 para n ≥ 1 y a2 = 18.

Solución. La solución general es an = 3n a0 . Como a2 = 32 a0 = 18 te-

nemos a0 = 2 y por lo tanto an = 2 · 3n .

La siguiente relación de recurrencia no tiene coeficientes constantes pero

se puede aplicar un cambio de variable.

Ejemplo 2. Determine (an ) si an − 2nan−1 = 0 para n ≥ 1 y a0 = 3.

Solución. Si hacemos el cambio de variable an = n!bn nos queda:

n!bn − 2n(n − 1)!bn−1 = 0. Dividiendo entre n! de ambos lados nos que-
da bn − 2bn−1 = 0. Luego bn = 2n b0 . Como a0 = 0!b0 = 3 tenemos b0 = 3 asi
que bn = 3 · 2n . Luego an = 3n!2n para n ≥ 0.

0.3. Recurrencia lineal homogenea de segundo orden

Tenemos una relación del tipo c0 an + c1 an−1 + c2 an−2 = 0 con a, b, c ∈ R
y ac 6= 0. El polinomio caracterı́stico es p(λ) = c0 λ2 + c1 λ + c2 . Tenemos 3
posibilidades para p(λ):

1. Dos raices reales distintas λ1 , λ2 . Una base de soluciones es {λn1 , λn2 }

luego la solución general es an = α1 λn1 + α2 λn2 .

2. Una raiz real doble λ1 . En este caso una base de soluciones es {λn1 , nλn1 }
luego la solución general es an = α1 λn1 + α2 λn2 .

3. Dos raices complejas conjugadas λ1 = a + bi, λ2 = a − bi (donde

a, b ∈ R). En este caso, como en el caso de raices reales distintas,
también {λn1 , λn2 } es una base de soluciones. Otra base de soluciones
que no involucra números complejos es {rn cos(nθ), rn sen(nθ)} donde

4
 λ1 = reiθ y λ2 = re−iθ es la expresión en coordenadas polares4 de
λ1 y λ2 , luego la solución general también puede expresarse como
an = αrn cos(nθ) + βrn sen(θ), para n ≥ 0.

Ejemplo 3. (raices reales distintas) Hallar la sucesión (an ) definida por

an+2 = 3an+1 − 2an , para n ≥ 0 y las condiciones iniciales a0 = 4, a1 = 5.

Solución. El polinomio caracterı́stico es p(λ) = λ2 − 3λ + 2 que tiene

raices 1 y 2 asi que {1n , 2n } forman una base de soluciones5 de la relación
homogenea (sin tener en cuenta las condiciones iniciales). La solución ge-
neral para la relación homogena es an = α + β2n . Como a0 = α + β = 4
y a1 = α + 2β = 5 obtenemos α = 3, β = 1. Luego la solución pedida es
an = 3 + 2n para n ≥ 0.

Ejemplo 4. (raiz real doble) Hallar la sucesión (an ) definida por an+2 =
4an+1 − 4an , para n ≥ 0 y las condiciones iniciales a0 = −1, a1 = 4.

Solución. El polinomio caracterı́stico es p(λ) = λ2 −4λ+4 que tiene raiz

doble 2, luego una base de soluciones para la recurrencia es {2n , n2n }. La so-
lución general es an = α2n +βn2n . Como a0 = α = −1 y a1 = 2α+2β = 4 ob-
tenemos α = −1, β = 3. Luego la sucesión que buscamos es an = (3n−1)·2n .

Ejemplo 5 (raices complejas conjugadas) Hallar la sucesión (an ) defini-

da por an+2 = 2an+1 − 2an , para n ≥ 0 y las condiciones iniciales a0 = 1,
a1 = 2.

Solución 1. El polinomio caracterı́stico es p(λ) = λ2 − 2λ + 2 con

raices complejas 1 + i y 1 − i. Una base de soluciones para la recurren-
cia es {(1 + i)n , (1 − i)n }. Luego nuestra solución es de la forma an =
α(1 + i)n + β(1 − i)n . Como a0 = α + β = 1 y a1 = (1 + i)α + (1 − i)β = 2 te-
nemos α = 1−i 1+i
2 , β = 2 luego la sucesión buscada viene dada por la fórmula
n n
an = (1−i)(1+i) +(1+i)(1−i)
2 para n ≥ 0. Observar que como (1 − i)(1 + i) = 2
también tenemos an = (1 + i)n−1 + (1 − i)n−1 para n ≥ 1, a0 = 1.

4
√
(La relación entre coordenadas cartesianas y polares viene dada por: r = a2 + b2 ,
θ = Arctg(b/a) si a 6= 0 y θ = π/2 si a = 0.
5
Atención: 1n debe interpretarse como la sucesión (bn ) identicamente 1, es decir bn = 1
para todo n ≥ 0. De la misma forma 2n debe interpretarse como la sucesión (cn ) definida
por cn = 2n para todo n ≥ 0. Es decir, los elementos de la base son sucesiones y no
números.

5
 √ π
Solución 2. Las raices del polinomio caracterı́stico son 1 + i = 2e 4 i
√ −π
y 1 −√i = 2e 4 i por√ lo tanto otra base de soluciones para la recurrencia
es {( 2) cos( 4 ), ( 2) sen( nπ
n nπ n
4 )}. Como nuestra sucesión verifica la recu-
√ √ n
rrencia entonces an = α( 2)n cos( nπ
4 ) + β( 2) sen( nπ
4 ). Con a0 = α = 1 y
√ √2 √ √2
a1 = α · 2 · 2 + β · 2 · 2 = α + β = 2 tenemos α = 1, β = 1. Luego la
√
sucesión buscada viene dada por la fórmula an = ( 2)n (cos( nπ nπ
4 ) + sen( 4 )).

Comentario: Cualquiera de las dos soluciones se darán como correctas

en las pruebas de este curso. Para el que tenga más familiaridad con núme-
ros complejos puede que le convenga trabajar con la base trigonométrica ya
que usualmente exige hacer menos cuentas, pero por otra parte debe de ex-
presar las raices del polinomio caracterı́stico en coordenadas polares y solo
en algunos pocos casos el argumento θ va a quedar lindo (lindo = múltiplo
racional de π).

Ejemplo 6 (raices complejas conjugadas) Hallar la sucesión (an ) defini-

da por an+2 = −2an , para n ≥ 0 y las condiciones iniciales a0 = 1, a1 = 2.

√ Solución.
√ Podemos calcular el polinomio caracterı́stico λ2 + 2 con raices
2i y −2i y proceder como en el ejemplo anterior. Otra posibilidad es ob-
servar que a partir de a0 podemos calcular de forma simple todos los términos
pares: a2 = −2a0 , a4 = −2a2 = (−2)2 a0 , a6 = −2a4 = (−2)3 a0 y en general
a2m = (−2)m a0 para todo m ≥ 0 (que puede probarse por inducción por
ejemplo). También a partir de a1 podemos calcular los términos impares:
a3 = (−2)a1 , a5 = (−2)2 a1 , a7 = (−2)3 a1 y en general a2m+1 = (−2)m a1
para m ≥ 0. Entonces la sucesión pedida puede expresarse por la fórmula
(−2)m

si n = 2m;
(an )n≥0 : an = donde m ∈ N.
2 · (−2)m si n = 2m + 1.

0.4. Relaciones en recurrencia lineal no homogenea

Como mencionamos anteriormente, una relación de recurrencia lineal de
orden k es una relación de la forma:

c0 an + c1 an−1 + · · · + ck an−k = f (n), ∀n ≥ k (5)

donde k ∈ Z+ y c0 , c1 , . . . , ck ∈ R con c0 ck 6= 0.

La observación clave es que si tenemos dos sucesiones (an ) y (bn ) que

verifican (5) entonces la sucesión diferencia (cn ): cn = an − bn verifica la

6
recurrencia lineal homogenea asociada:

c0 an + c1 an−1 + · · · + ck an−k = 0, ∀n ≥ k (6)

Si queremos hallar una sucesión (an ) que satisfaga (5) con ciertas con-
diciones iniciales para a0 , a1 , . . . , ak−1 entonces alcanza hallar una solución
(p) (p)
particular6 (an ) de (5). La sucesión (bn ): bn = an − an verifica una rela-
ción lineal homogenea, que sabemos resolver en el caso de orden 1 ó 2. En
(p)
resumen, todo se resume a hallar una solución particular (an ).

Búsqueda de la solución particular: Nosotros solo vamos a consi-

derar el caso en que f (n) = rn g(n) donde g(n) es un polinomio de grado t
y r ∈ R (o suma de funciones de esta forma). Observar que esto incluye el
caso en que f (n) sea un polinomio (r = 1) y también el caso en que f (n) sea
exponencial (p ≡ 1). Basados en consideraciones que se hacen en la página
490 del Grimaldi (incluida la tabla 10.2) tenemos lo siguiente:
Si r no es raiz del polinomio caracterı́stico7 de la recurrencia homo-
genea asociada entonces existe una solución particular de la forma
(p)
an = rn h(n) donde h(x) es un polinomio8 del mismo grado que g(n)
.

Si r es raiz simple del polinomio caracterı́stico de la recurrencia ho-

mogenea asociada entonces existe una solución particular de la forma
(p)
an = nrn h(n) donde h(n) es un polinomio del mismo grado que g(n).

Si r es raiz doble del polinomio caracterı́stico de la recurrencia ho-

mogenea asociada entonces existe una solución particular de la forma
(p)
an = n2 rn h(n) donde h(n) es un polinomio del mismo grado que
g(n).
(p)
En general siempre habrá una solución particular de la forma an =
ns rn h(n) donde h(n) es un polinomio del mismo grado que g(n) y s es la
multiplicidad de r como raiz del polinomio caracterı́stico de la recurrencia
homogenea. Como estamos trabajando solamente con recurrencias de orden
1 y 2 nos basta considerar los tres casos mencionados arriba.

6
Solución particular significa que es solución de la recurrencia no homogenea (5) pero
no necesariamente verifica las condiciones iniciales que queremos.
7
Cuidado de no confundir el polinomio caracterı́stico con el polinomio g(n).
8
Los coeficientes de h(n) los obtenemos substituyendo (apn ) en la recurrencia no homo-
genea (5).

7
 Ejemplo 7. Determine la sucesión (an ) definida por la recurrencia an+2 =
3an+1 − 2an + n2 y condiciones iniciales a0 = 0, a1 = −2.

Solución. Primero hallamos la solución general de la recurrencia homo-

genea asociada an+2 = 3an+1 − 2an (ver ejemplo 3). El polinomio carac-
terı́stico es p(λ) = λ2 − 3λ + 2 con raices 1 y 2, la solución general de la
(H)
homogenea es an = α + β2n con α, β ∈ R.

Ahora debemos hallar una solución particular. En este ejemplo el término

(P )
independiente es f (n) = rn g(n) con r = 1 y g(n) = n2 por lo tanto an =
(P )
n · 1n · (an2 + bn + c) = an3 + bn2 + cn. Calculamos an+2 e igualamos con
(P ) (P )
3an+1 − 2an + n2 para determinar los valores de a, b y c.

(P )
an+2 = a(n + 2)3 + b(n + 2)2 + c(n + 2)
= an3 + (6a + b)n2 + (12a + 4b + c)n + (8a + 4b + 2c)

(P )
3an+1 − 2a(P ) 2 3 2 3 2
n + n = 3(a(n + 1) + b(n + 1) + c(n + 1)) − 2(an + bn + cn) + n
2

= 3an3 + (9a + 3b)n2 + (9a + 6b + 3c)n + (3a + 3b + 3c) − 2(an3 + bn2 + cn) + n2
= an3 + (9a + b + 1)n2 + (9a + 6b + c)n + (3a + 3b + 3c).

 6a + b = 9a + b + 1
Obtenemos el sistema de ecuaciones: 12a + 4b + c = 9a + 6b + c
8a + 4b + 2c = 3a + 3b + 3c

Lo resolvemos y obtenemos a = −1/3, b = −1/2, c = −13/6.

Como la diferencia entre dos soluciones es solución de la homogenea

(P ) (P ) 3 2
asociada: an − an = α + β2n , n ≥ 0 donde an = −( n3 + n2 + 13n 6 ).
Con n = 0 y n = 1 obtenemos 0 − 0 = α + β y (−2) + 3 = α + 2β. Luego
3 2 2n3 +3n2 +13n+6
α = −1, β = 1 y an = −( n3 + n2 + 13n n
6 )−1+2 =2 −
n
6 .

0.5. Principio de superposición

(1)
Si tenemos una sucesión (an ) que verifica una recurrencia
(E1) Aan + Ban−1 + Can−2 = f1 (n)
(2)
y una sucesión (an ) que verifica una recurrencia
(E2) Aan + Ban−1 + Can−2 = f2 (n),

8
 (1) (2)
entonces la sucesión (αan + βan ) verifica la recurrencia

(E) Aan + Ban−1 + Can−2 = αf1 (n) + βf2 (n).

Esta observación es útil para hallar una solución particular de una recu-
rrencia (E) Aan + Ban−1 + Can−2 = f (n) donde f (n) es complicada pero
puede expresarse como una combinación lineal f (n) = αf1 (n) + βf2 (n) de
funciones más simples f1 (n) y f2 (n).

Ejemplo 8. Hallar la sucesión (an ) que verifica la relación de recurren-

cia an+2 − 2an+1 + an = 3n − 2n para n ≥ 0, con las condiciones iniciales
a0 = a1 = 0.

Solución. El polinomio caracterı́stico de la recurrencia homogenea aso-

ciada es p(λ) = λ2 − 2λ + 1 con raiz doble 1, una base de soluciones es
{1n , n · 1n } y por lo tanto la solución general de la homogenea es de la forma
(H)
an = α + βn con α, β ∈ R. Para determinar una solución particular de
la recurrencia original que llamamos (E), vamos a determinar una solución
(1)
particular (an ) para

(E1) an+2 − 2an+1 + an = 3n

(2)
y una solución particular (an ) para

(E2) an+2 − 2an+1 + an = 2n ,

(P ) (1) (2)
luego por el principio de superposición la sucesión an = an − an será una
solución particular de (E). Como 3 no es raiz del polinomio caracterı́stico
(1)
sabemos que hay una solución particular de (E1) de la forma an = A3n
con A ∈ R. Substituyendo en (E1) obtenemos A3n+2 − 2A3n+1 + A3n =
(1) n
3n ⇔ 9A − 6A + A = 1 ⇔ 4A = 1 ⇔ A = 1/4, asi que an = 34 .
(2)
Como 2 no es raiz de (E2) tenemos una solución particular an = B2n
con B ∈ R. Substituyendo en (E2) obtenemos B2n+2 − 2B2n+1 + B2n =
(2)
2n ⇔ 4B − 4B + B = 1 ⇔ B = 1, asi que an = 2n . Por el principio de
superposición una solución particular de la recurrencia original viene dada
(P ) n (P )
por an = 34 − 2n . Como an − an verifica la homogenea asociada tenemos
(P )
an − an = α + βn. Utilizamos las condiciones iniciales a0 = a1 = 0 junto
(P ) (P )
con a0 = −3/4 y a1 = −5/4 para obtener α y β. Con n = 0 tenemos
3/4 = α y con n = 1 tenemos 5/4 = α + β ⇒ β = 5/4 − α = 1/2. Luego
n n n+2
an = 34 − 2n + 34 + n2 = 3 −2 4 +3+2n para todo n ≥ 0.

9
0.6. Método de las funciones generatrices
La sección del libro de Grimaldi para estudiar estos temas es la 10.4. El
método de las funciones generatrices es un método alternativo para resolver
relaciones de recurrencias y consiste en los siguientes pasos:

1. Usar la relación de recurrencia para construir una ecuación de funcio-

nes generatrices cuya incógnita sea la función generatriz A(x) de la
sucesión (an ) que queremos determinar.

2. Expresar A(x) como un cociente de polinomios.

3. Usar el método de fracciones simples para expresar A(x) como suma

de fracciones simples.

4. Utilizar la fórmula (1 − x)−k = ∞ k−1+n n

P

n=0 k−1 x en cada fracción sim-
ple para luego obtener an comparando coeficientes n-ésimos de cada
lado de la igualdad.

Ejemplo 9. Hallar la sucesión (an ) que verifica la relación de recurren-

cia an+2 − 2an+1 + an = 3n para n ≥ 0, con a0 = 0 y a1 = 1.
P∞ n
Solución. Llamamos A(x) = n=0 an x a la función generatriz que
queremos determinar. El primer paso es observar que la igualdad an+2 −
2an+1 + an = 3n para n ≥ 0 equivale a la igualdad de funciones generatrices:
∞
X ∞
X
n+2
(an+2 − 2an+1 + an )x = 3n xn+2 .
n=0 n=0

(el xn+2 corresponde al mayor ı́ndice que aparece de la sucesión que es an+2 )
Esta ecuación equivale a:
∞
X ∞
X ∞
X ∞
X
an+2 xn+2 − 2x an+1 xn+1 + x2 an xn = x2 3n xn
n=0 n=0 n=0 n=0
X∞
(A(n) − a0 − a1 x) − 2x(A(x) − a0 ) + x2 A(n) = x2 (3x)n .
n=0
P∞ n 1
Usando que a0 = 0, a1 = 1 y n=0 (3x) = 1−3x tenemos:

x2 x − 2x2
(1 − 2x − x2 )A(x) − x = ⇒ A(x) = .
1 − 3x (1 − x)2 (1 − 3x)

10
Con esto hemos conseguido el paso 2 el método (expresar A(x) como co-
ciente polinomial). El tercer paso es expresar A(x) como suma de fracciones
simples, para ello debemos determinar a, b, c ∈ R tal que:

x − 2x2 a b c
2
= + 2
+
(1 − x) (1 − 3x) 1 − x (1 − x) 1 − 3x
⇔ x − 2x = a(1 − x)(1 − 3x) + b(1 − 3x) + c(1 − x)2
2

⇔ x − 2x2 = a(1 − 4x + 3x2 ) + b(1 − 3x) + c(1 − 2x − x2 ).

Con x = 1 obtenemos −1 = −2b ⇒ b = 12 y con x = 31 obtenemos

1
3 − 92 = 4c 1
9 ⇒ c = 4 . Con x = 1 en 1 − 4x = a(−4 + 6x) + b(−3) + c(−2 + 2x)
(que se obtiene derivando de ambos lados) obtenemos −3 = 2a − 3b =
2a − 3/2 ⇒ a = −3
4 . Asi que tenemos:

3 1 1
A(x) = − · (1 − x) + · (1 − x)−2 + · (1 − 3x)−1
4 2 4
∞ ∞   ∞
3 X
n 1 X 1+n n 1 X
=− · x + · x + · (3x)n
4 2 1 4
n=0 n=0 n=0
∞   ∞  
X 3 1 1 n n
X 1 1 1 n
= − + (1 + n) + · 3 x = − + · n + · 3 xn .
4 2 4 4 2 4
n=0 n=0

Luego an = − 41 + 1
2 ·n+ 1
4 · 3n , para n ≥ 0.

El método de las funciones generatrices también sirve para resolver sis-

tema de relaciones de recurrencia que involucran dos sucesiones (an ) y (bn ).
Los pasos son escencialmente los mismos, primero usar las
P∞ relaciones de recu-
rrencia
P∞ para obtener un sistema con incógnitas A(x) = n=0 an xn y B(x) =
n
n=0 an x . Resolver ese sistema para obtener A(x) y B(x). Expresar estas
funciones generatrices primero como cociente de polinomios,Pluego como
su-
ma de fracciones simples, utilizar la fórmula (1 − x)−k = ∞ n=0
k−1+n n
k−1 x
y comparar coeficientes para obtener expresiones para an y bn en función
de n (ver Ej. 10.35, pág. 497 del libro de Grimaldi para un ejemplo con-
creto). Se puede ver también un ejemplo resuelto en detalle en el video:
https://www.youtube.com/watch?v=rLQr0iOeYWg&t=4s.

11