Capı́tulo 3: Técnicas de Conteo

Clase 3: Conteo utilizando relaciones de

recurrencia

Matemática Discreta - CC3101

Profesor: Pablo Barceló

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 1 / 25

 Motivación

Muchos problemas de conteo no pueden ser resueltos con las

técnicas que hemos visto hasta ahora.

Ejemplo: ¿Cuántos strings de largo n no contienen dos 0s

consecutivos?

Para resolver algunos de estos problemas utilizaremos las relaciones

de recurrencia.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 2 / 25

 Relaciones de recurrencia

Definición
Una relación de recuurencia para la secuencia {an } es una ecuación
que expresa an en términos de a0 , a1 , . . . , an−1 , para todo entero
n ≥ n0 .
Una secuencia es una solución de la relación de recurrencia si
satisface los términos de la relación.

Ejercicio: ¿Es an = 3n una solución para la relación de recurrencia

an = 2an−1 − an−2 , para n = 2, 3, 4 . . . ? ¿Es an = 2n una solución?
¿Es an = 5 una solución?
Para poder determinar exactamente una secuencia además
necesitamos entregar sus condiciones iniciales.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 3 / 25

 Ejemplo de relación de recurrencia

Ejercicio: Usted deposita $1000 en su cuenta de ahorro que da un

11 % de interés anual. ¿Cuánto tendrá en 30 años?

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 4 / 25

 Ejemplo de relación de recurrencia

Ejercicio: Usted deposita $1000 en su cuenta de ahorro que da un

11 % de interés anual. ¿Cuánto tendrá en 30 años?
Note que P0 = 1000 y que para cada n ≥ 0, Pn+1 = Pn + 0, 11Pn .
Una ecuación explı́cita para Pn es (1, 11)n P0 = (1, 11)n · 1000.
Por último, P30 ≈ 22900.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 4 / 25

 Otro ejercicio

Ejercicio: Asuma que deja un par de conejos en una isla. Los

conejos no se reproducen hasta que tienen 2 meses. Después de los
dos meses, cada conejo produce un nuevo par de conejos
mensualmente. Los conejos no mueren.
Encuentre una relación de recurrencia que exprese el número de
pares de conejos en el mes n.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 5 / 25

 Otro ejercicio

Ejercicio: Asuma que deja un par de conejos en una isla. Los

conejos no se reproducen hasta que tienen 2 meses. Después de los
dos meses, cada conejo produce un nuevo par de conejos
mensualmente. Los conejos no mueren.
Encuentre una relación de recurrencia que exprese el número de
pares de conejos en el mes n.

Condición inicial: f0 = 1 y f1 = 1.
Relación de recurrencia: # de conejos el mes n = # de conejos en
mes n − 1 + nuevos pares de conejos.
Por tanto, fn = fn−1 + fn−2 , para todo n ≥ 2.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 5 / 25

 Torres de Hanoi
Las torres de Hanoi son un puzzle popular del siglo XIX, que
consiste de 3 barras montadas en un tablero y una serie de discos
de diferente tamaño. La configuración inicial de los discos es como
se muestra a continuación.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 6 / 25

 Torres de Hanoi: Reglas y objetivo

Las reglas del juego permiten traspasar discos de a uno, de una

barra a otra, de tal modo que nunca un disco quede arriba de un
disco más chico.
El objetivo del juego es traspasar todos los discos a otra barra, en
orden de tamaño.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 7 / 25

 Ejercicio de torres de Hanoi

Ejercicio: Defina una relación de recurrencia {Hn } que determine el

número de movidas necesarias para resolver el problema de las
torres de Hanoi con n discos. Luego resuélvala.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 8 / 25

 Ejercicio de torres de Hanoi

Ejercicio: Defina una relación de recurrencia {Hn } que determine el

número de movidas necesarias para resolver el problema de las
torres de Hanoi con n discos. Luego resuélvala.

La respuesta es H1 = 1 y Hn = 2Hn−1 + 1, para n ≥ 2.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 8 / 25

 Ejercicio de torres de Hanoi

Ejercicio: Defina una relación de recurrencia {Hn } que determine el

número de movidas necesarias para resolver el problema de las
torres de Hanoi con n discos. Luego resuélvala.

La respuesta es H1 = 1 y Hn = 2Hn−1 + 1, para n ≥ 2.

Por tanto, Hn = 2n − 1.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 8 / 25

 Ejercicios finales

Ejercicio: Un string de números decimales es válido si contiene un

número par de 0s. Defina una relación de recurrencia {cn } que
entrega el número de strings válidos de largo n.
Ejercicio: Defina recursivamente la sucesión {an } que da la
cantidad de strings de largo n que tienen dos 0s consecutivos.
Ejercicio: Defina recursivamente la sucesión {bn } que da la
cantidad de strings de largo n que no tienen tres 0s consecutivos.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 9 / 25

 Más ejercicios finales

En estos ejercicios considere alfabeto ternario {a, b, c}.

Ejercicio: Defina recursivamente la sucesión {cn } que da la

cantidad de strings de largo n que no tienen dos a’s consecutivas.
Ejercicio: Defina recursivamente la sucesión {dn } que da la
cantidad de strings de largo n que no tienen ni dos a’s ni dos b’s
consecutivas.
Ejercicio: Defina recursivamente la sucesión {en } que da la
cantidad de strings de largo n que no tienen ni dos a’s ni dos b’s ni
dos c’s consecutivas.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 10 / 25

 Resolviendo relaciones de recurrencia

Como hemos visto, las relaciones de recurrencia ocurren

naturalmente al momento de modelar problemas de conteo.

Esto naturalmente genera el problema de cómo resolver estas

relaciones de recurrencia.

Muchas veces esto no es fácil, pero desarrollaremos una técnica

para al menos una clase de estas relaciones: Las relaciones de
recurrencia lineales con coeficientes constantes.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 11 / 25

 Relaciones de recuurencia lineales y homogeneas

Comenzaremos con un caso particular de esta clase de relaciones

de recurrencia:
Definición
Una relación de recurrencia es lineal, homogenea y tiene
coeficientes enteros si es de la forma

an = c1 an−1 + c2 an−2 + · · · + ck an−k ,

donde c1 , c2 , . . . , ck son números reales y ck 6= 0. Decimos que la

relación en este caso es de grado k.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 12 / 25

 Relaciones de recuurencia lineales y homogeneas

Comenzaremos con un caso particular de esta clase de relaciones

de recurrencia:
Definición
Una relación de recurrencia es lineal, homogenea y tiene
coeficientes enteros si es de la forma

an = c1 an−1 + c2 an−2 + · · · + ck an−k ,

donde c1 , c2 , . . . , ck son números reales y ck 6= 0. Decimos que la

relación en este caso es de grado k.
La relación de recurrencia:
◮ 2
an = an−1 no es lineal;
◮ an = an−1 + 1 no es homogenea;
◮ an = nan−1 no tiene coeficientes enteros.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 12 / 25

 Resolviendo estas relaciones de recurrencia

Estudiamos este tipo de relaciones de recurrencia porque a menudo

aparecen al modelar problemas, y porque pueden ser resueltas
sistemáticamente.
La idea es tratar de buscar soluciones de la forma r n , donde r es
una constante.
Note que esto es cierto si y sólo si:

r n = c1 r n−1 + c2 r n−2 + · · · + ck r n−k

O equivalentemente:

r k − c1 r k−1 − c2 r k−2 − · · · − ck = 0.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 13 / 25

 Resolviendo estas relaciones de recurrencia

Estudiamos este tipo de relaciones de recurrencia porque a menudo

aparecen al modelar problemas, y porque pueden ser resueltas
sistemáticamente.
La idea es tratar de buscar soluciones de la forma r n , donde r es
una constante.
Note que esto es cierto si y sólo si:

r n = c1 r n−1 + c2 r n−2 + · · · + ck r n−k

O equivalentemente:

r k − c1 r k−1 − c2 r k−2 − · · · − ck = 0.

Por tanto, la secuencia {an } = r n es una solución a la relación de

recurrencia si y sólo si es solución de la ecuación anterior (llamada
ecuación caracterı́stica).

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 13 / 25

 Relaciones de recurrencia de grado 2

Para simplificar la presentación estudiaremos primero relaciones de

recurrencia como las antes mostradas pero de grado 2.

Teorema
Sean c1 , c2 números reales y asuma que r 2 − c1 r − c2 = 0 tiene
dos raı́ces distintas r1 y r2 . Entonces la secuencia {an } es una
solución a la relación de recurrencia an = c1 an−1 + c2 an−2 si y sólo
si an = α1 r1n + α2 r2n para n = 0, 1, 2, . . . donde α1 y α2 son
constantes.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 14 / 25

 Demostración del teorema

Asuma primero que an = α1 r1n + α2 r2n .

Ya que r1 y r2 son raı́ces, r12 = c1 r1 + c2 y r22 = c1 r2 + c2 .
Por tanto,

c1 an−1 + c2 an−2 = c1 (α1 r1n−1 + α2 r2n−1 ) + c2 (α1 r1n−2 + α2 r2n−2 )

= α1 r1n−2 (c1 r1 + c2 ) + α2 r2n−2 (c1 r2 + c2 )
= α1 r1n + α2 r2n
= an

Concluimos que {an } = {α1 r1n + α2 r2n } es una solución a la

relación de recurrencia.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 15 / 25

 Demostración del teorema

Asuma ahora que {an } es solución para an = c1 an−1 + c2 an−2 .

Demostraremos que an = α1 r1n + α2 r2n , para algún α1 y α2 .
Considere condiciones iniciales a0 = K0 y a1 = K1 .
Entonces deberı́amos tener que a0 = K0 = α1 + α2 y
a1 = K1 = α1 r1 + α2 r2 .
Obtenemos entonces que
◮ α1 = (C1 − C0 r2 )/(r1 − r2 ).
◮ α2 = (C0 r1 − C1 )/(r1 − r2 ).

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 16 / 25

 Demostración del teorema

Sean α0 y α1 como los calculamos recién.

Ya sabemos que an = α1 r1n + α2 r2n es solución. Además, satisface
las condiciones iniciales.
Luego
{an } = {α1 r1n + α2 r2n }
porque solo existe una solución para an = c1 an−1 + c2 an−2 que
satisface las condiciones iniciales.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 17 / 25

 Ejercicios

Ejercicio: Encuentre la solución a la relación de recurrencia

an = an−1 + 2an−2 , con a0 = 2 y a1 = 7.

Ejercicio: Encuentre una solución explı́cita a los números de

Fibonacci.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 18 / 25

 Ecuaciones con solo una raı́z

Note que en la demostración anterior usamos esencialmente el

hecho de que la ecuación tenı́a dos raı́ces distintas (¿dónde?).
¿Qué pasa cúando tenemos una sola raı́z?

Teorema
Sean c1 , c2 números reales y asuma que r 2 − c1 r − c2 = 0 tiene
como única raı́z a r0 . Entonces la secuencia {an } es una solución a
la relación de recurrencia an = c1 an−1 + c2 an−2 si y sólo si
an = α1 r0n + α2 nr0n para n = 0, 1, 2, . . . donde α1 y α2 son
constantes.

Ejercicio: ¿Cuál es la solución de la relación de recurrencia

an = 6an−1 − 9an−2 , con a0 = 1 y a1 = 6?

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 19 / 25

 Relaciones de recurrencia de grado k

Generalizemos los resultados anteriores (demostraciones son

similares):

Teorema
Sean c1 , c2 , . . . , ck números reales y asuma que
r k − c1 r k−1 − · · · − ck = 0 tiene k distintas raı́ces r1 , . . . , rk .
Entonces la secuencia {an } es una solución a la relación de
recurrencia an = c1 an−1 + c2 an−2 + · · · + ck an−k si y sólo si
an = α1 r1n + α2 r2n + · · · + αk rkn para n = 0, 1, 2, . . . donde
α1 , α2 , . . . , αk son constantes.

Ejercicio: Resuelva la relación de recurrencia

an = 6an−1 − 11an−2 + 6an−3 tal que a0 = 2, a1 = 5 y a2 = 15.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 20 / 25

 Relaciones de recurrencia de grado k
Y finalmente, el caso más general.
Teorema
Sean c1 , c2 , . . . , ck números reales y asuma que
r k − c1 r k−1 − · · · − ck = 0 tiene t distintas raı́ces r1 , . . . , rt con
multiplicidades m1 , m2 , . . . , mt . Entonces la secuencia {an } es una
solución a la relación de recurrencia
an = c1 an−1 + c2 an−2 + · · · + ck an−k si y sólo si

an = (α1,0 + α1,1 n + · · · + α1,m1 −1 nm1 −1 )r1n

+ (α2,0 + α2,1 n + · · · + α2,m2 −1 nm2 −1 )r2n
+ · · · + (αt,0 + αt,1 n + · · · + αt,mt −1 nmt −1 )rtn

para n = 0, 1, 2, . . . donde todos los αi ,j son constantes.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 21 / 25

 Relaciones de recurrencia de grado k
Y finalmente, el caso más general.
Teorema
Sean c1 , c2 , . . . , ck números reales y asuma que
r k − c1 r k−1 − · · · − ck = 0 tiene t distintas raı́ces r1 , . . . , rt con
multiplicidades m1 , m2 , . . . , mt . Entonces la secuencia {an } es una
solución a la relación de recurrencia
an = c1 an−1 + c2 an−2 + · · · + ck an−k si y sólo si

an = (α1,0 + α1,1 n + · · · + α1,m1 −1 nm1 −1 )r1n

+ (α2,0 + α2,1 n + · · · + α2,m2 −1 nm2 −1 )r2n
+ · · · + (αt,0 + αt,1 n + · · · + αt,mt −1 nmt −1 )rtn

para n = 0, 1, 2, . . . donde todos los αi ,j son constantes.

Ejercicio: Solucione an = −3an−1 − 3an−2 − an−3 con a0 = 1,

a1 = −2 y a2 = −1.
P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 21 / 25
 Ejercicio de recurrencias simultaneas

Ejercicio: Resuelva las siguientes relaciones de recurrencias

simultaneas:

an = 3an−1 + 2bn−1
bn = an−1 + 2bn−1

Asuma a0 = 1 y b0 = 2.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 22 / 25

 Relaciones de recurrencia no homogeneas

Asuma que an = c1 an−1 + c2 an−2 + · · · + ck an−k + f (n) es una

relación de recurrencia no homogenea.
Llamamos a an = c1 an−1 + c2 an−2 + · · · + ck an−k su relación de
recurrencia homogenea asociada.
Entonces las soluciones de esta relación de recurrencia tienen una
forma particular:
Teorema
(p)
Si {an } es una solución de la relación de recurrencia
an = c1 an−1 + c2 an−2 + · · · + ck an−k + f (n), entonces toda
(p) (h) (h)
solución es de la forma {an + an }, donde {an } es una solución
de la relación de recurrencia homogenea asociada.

Ejercicio: Demuestre el teorema.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 23 / 25

 Soluciones para relaciones de recurrencia no homogeneas
La clave está entonces en obtener una solución para la relación de
recurrencia no homogenea. Esto podemos lograrlo para algunos
casos:
Teorema
Sea {an } definido como an = c1 an−1 + c2 an−2 + · · · ck an−k + f (n),
y asuma que

f (n) = (bt nt + bt−1 nt−1 + · · · + b1 n + b0 )s n ,

donde b0 , b1 , . . . , bt y s son números reales. Entonces,

◮ Si s no es “raı́z” de la relación de recurrencia asociada, entonces
existe una solución particular de la forma
(pt nt + pt−1 nt−1 + · · · + p1 n + p0 )s n .
◮ Si s es “raı́z” de la relación de recurrencia asociada con
multiplicidad m, entonces existe una solución particular de la forma
nm (pt nt + pt−1 nt−1 + · · · + p1 n + b0 )s n .
P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 24 / 25
 Ejercicios finales

Ejercicio: Encuentre la forma de una solución para

an = 6an−1 − 9an−2 + f (n) cuando f (n) = n3n y cuando
f (n) = (n2 + 1)2n .

Ejercicio: Defina la recurrencia {sn } que define la suma de los

primeros n números naturales. Luego resuélvala utilizando el
teorema anterior.

P. Barceló – Matemática Discreta - Cap. 3: Técnicas de Conteo 25 / 25