UNIVERSIDAD NACIONAL DE COLOMBIA SEDE BOGOTÁ
SISTEMAS NUMÉRICOS
TALLER 3
Algunos de los ejercicios han sido propuestos por la Prof. Margarita Ospina
I) Demuestre que:
n n n
2k = 2n+1 − 1. 3k = 23 3n − 1
4k = 43 4n − 1
P P P
a) b) 2 c) 3
k=0 k=0 k=0
n 1
bk = bn+1 − 1 si b es un entero mayor o igual que 2.
P
d)
k=0 b−1
II) a) En las siguientes sucesiones definidas recursivamente halle los seis primeros
términos, o los que necesite, para encontrar una fórmula directa (no recursiva)
de an y demuéstrela.
i) a0 = 1 y an+1 = 3an + 1 para n > 0.
ii) a0 = 1 y an+1 = 5an + 1 para n > 0.
iii) a0 = 3 y an = an−1 + n para n > 1.
iv) a0 = 2, a1 = 3 y an = an−1 an−2 si n > 1.
b) Sea a0 = 2, a1 = 5 y an = 5an−1 − 6an−2 si n > 1, halle los seis primeros
términos de la sucesión y demuestre que an = 2n + 3n .
c) En cada caso deduzca una fórmula de recurrencia que defina la sucesión dada
i) cn = n2 + 1 ii) cn = 2n3 + n.
III) Se define la sucesión de Fibonacci en forma recursiva ası́: F0 := 1, F1 := 1
y Fn := Fn−1 + Fn−2 para todo n ≥ 2.
a) Escriba los diez primeros términos de la sucesión.
b) Demuestre las siguientes propiedades: (si es necesario, establezca a partir de
qué n se cumplen)
Fn+1 + Fn−2 n
P
i) Fn = ii) Fk = Fn+2 − 1
2 k=1
n
P n
P
iii) F2k−1 = F2n iv) F2k = F2n+1 − 1
k=1 k=1
n
Fk2 = Fn Fn+1 vi) Fn+1 Fn−1 − Fn2 = (−1)n (Identidad de Cassini)
P
v)
k=1
vii) Si 3 | n entonces 2 | Fn viii) Si 4 | n entonces 3 | Fn
1
IV) Una pareja de conejos jóvenes con capacidad de reproducirse entre sı́ se
dejan en una isla. Un par de conejos no se reproduce sino a partir de los dos
meses de edad. Al momento en que ellos han cumplido dos meses de edad, cada
par de conejos produce cada mes otro par de conejos jóvenes con capacidad de
reproducirse entre sı́.
Encuentre una relación de recurrencia para el número de pares de conejos en la
isla después de n meses, suponiendo que ninguno de los conejos se muere.
V) Encuentre una relación de recurrencia y dé condiciones iniciales para el
número de cadenas de 0’s y 1’s de longitud n que no tienen dos 0’s consecutivos.
a) ¿Cuántas de esas cadenas de longitud 5 hay?
b) ¿Cuántas de esas cadenas de longitud n hay?
VI) Enumeración de Códigos: Un sistema de computadores considera
que una cadena de dı́gitos decimales es válida si contiene un número par de 0’s.
Por ejemplo, 1230407869 es válida, pero 120987045608 no es válida. Sea an el
número de códigos válidos de n dı́gitos.
Encuentre una relación de recurrencia para an .
VII) Denotamos por d2 (n) el número de formas de escribir a n como sumas
de 1’s y 2’s, en las que importa el orden. Estas diferentes formas de escribir a
n como suma de otros enteros se les denominan composiciones. Por ejemplo,
d2 (3) = 3, y sus composiciones son
1+1+1, 1+2, 2+1
• Calcule d2 (5) mostrando las diferentes composiciones.
• Establezca una relación entre d2 (n) y la sucesión de Fibonacci. Demuéstrela.
• Denotamos por d` (n) el número de formas de escribir a n como sumas de
1’s, 2’s, . . . , `’s. Calcule d3 (4) mostrando las diferentes composiciones.
Encuentre una relación de recurrencia para d` (n) y demuéstrela.
VIII) Sea bn el número de permutaciones π en el conjunto [n] = {1, 2, . . . , n},
tal que |i − πi | ≤ 1 para todo 1 ≤ i ≤ n, donde n ≥ 1. En otras palabras, bn
cuenta el número de permutaciones que envı́an cada elemento a otro que diste
a lo más de una posición de su posición natural.
1. Calcule b4 mostrando las diferentes permutaciones.
2. Encuentre una recurrencia para bn . ¿Qué relación hay con los números de
Fibonacci?
