Taller 4 Matemáticas Discretas Escuela de Matemáticas − Facultad de Ciencias
Secc. 2.3 y 3.1 Código 3006906 Universidad Nacional de Colombia
Este taller es complemento de los ejercicios de las secciones 2.3 y 3.1 del texto guı́a: Johnsonbaugh, R.,
Matemáticas Discretas, Sexta Edición, Pearson, México, 2005.
1. Para la sucesión v definida por
vn = n! + 1, n ≥ 1.
Halle
4
P 3
P 5
Q n
Q
(a) vi (b) vk (c) vj (d) 2vi
i=2 k=3 j=3 i=n
2. Considere la sucesión b definida por
n
bn = (−1) · n, n ≥ 1.
(a) Calcule
4
X 5
X 6
X
bi , bi y bi .
i=1 i=1 i=1
n
P
(b) Halle una fórmula para la sucesión c definida por cn = bi .
i=1
2
Q 3
Q 4
Q
(c) Calcule bi , bi y bi .
i=1 i=1 i=1
n
Q
(d) Halle una fórmula para la sucesión d definida por dn = bi .
i=1
3. Sea x la sucesión definida por
x1 = 2, xn = 3 + xn−1 , n ≥ 2,
Halle una fórmula para la sucesión c definida por
n
X
cn = xi .
i=1
4. Sea u la sucesión definida por
u1 = 3, un = 3 + un−1 , n ≥ 2,
Halle una fórmula para la sucesión c definida por
n
Y
cn = ui .
i=1
5. Para la sucesión r definida por
rn = 3 · 2n − 4 · 5n , n ≥ 0,
pruebe que {rn } satisface
rn = 7 · rn−1 − 10 · rn−2 , n ≥ 2.
6. Muestre que la sucesión z definida por
zn = (2 + n) · 3n , n ≥ 0,
satisface
zn = 6 · zn−1 − 9 · zn−2 , n ≥ 2.
1
7. Reescriba la sumatoria
n
X
i2 rn−i ,
i=1
sustituyendo el ı́ndice i por k, donde i = k + 1.
8. Reescriba la sumatoria
n
X
Ck−1 Cn−k ,
k=1
sustituyendo el ı́ndice k por j, donde k = j + 1.
9. Proporcione ejemplos de relaciones en el conjunto A = {1, 2, 3, 4} que satisfagan a la vez las siguientes
propiedades:
(a) No reflexiva, no antisimétrica y no transitiva
(b) Reflexiva, antisimétrica y no transitiva
(c) R y S sean antisimétricas pero R ∪ S no sea antisimétrica
(d) f y g son funciones tal que f ◦ g es inyectiva pero f no es inyectiva.
10. Sea A = {1, 2, 3, 4, 5} B = {4, 5} y C = {2, 4}. Defina la relación R en el conjunto de partes de A, P (A) ,
como
R := {(X, Y ) : X ∪ B = Y ∪ B}
Demuestre que R es una relación: Reflexiva, simétrica y transitiva y liste los elementos del conjunto
[C] := {X ∈ P (A) : (X, C) ∈ R}.
11. Sea A = {a, b, c, d}. Dibuje el digrafo correspondiente a cada una de las siguientes relaciones en A y diga si la
relación es reflexiva, simétrica, antisimetrica o transitiva.
Calcule también las relaciones Ri ◦ Rj y sus correspondientes digrafos, para todo i, j = 1, · · · , 6.
a. R1 = {{(b, b), (b, c), (b, d), (c, b), (c, c), (c, d)}
b. R2 = {(a, b), (b, a)}
c. R3 = {(a, a), (b, b), (c, c), (d, d)}
d. R4 = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a)}
e. R5 = {(a, c), (a, d), (b, c), (b, d), (c, a), (c, d)}
f. R6 = {(a, b), (b, c), (c, d)}
12. Pruebe que si una relación R en un conjunto X es reflexiva, entonces Rn es reflexiva, para todo entero n ≥ 1.
13. Pruebe que si una relación R en un conjunto X es reflexiva y transitiva, entonces Rn = R para todo entero
n ≥ 1.
14. Pruebe que una relación R en un conjunto X es antisimetrica si y solo si R ∩ R−1 = {(x, x) | x ∈ X}.
15. Sea R la relación en el conjunto A = {1, 2, 3, 4, 5, 6, 7} definida por (a, b) ∈ R si y solo si 4 divide a (a − b) .
a) Liste todos los elementos de R, R−1 , R2 , R ∩ R−1 .
b) Para cada una de las relaciones de la parte a) haga un digrafo que lo represente.
c) Diga si R es reflexiva, simétrica, antisimetrica o transitiva. ¿Es R una relación de equivalencia?
16. Sea R una relación en un conjunto X. Sea SR la relación en X definida por: (x, y) ∈ SR si y solo si (x, y) ∈ R
y (y, x) ∈ R.
a. Si X = {1, 2, 3, 4} y R = {(1, 2), (1, 1), (2, 3)}. Encuentre SR .
b. Si X = {1, 2, 3, 4} y R = {(1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (5, 1)}. Encuentre SR .
c. Pruebe que si R es una relación reflexiva y transitiva, entonces SR es una relación de equivalencia.
17. a. Pruebe que sólo hay una relación de equivalencia en un conjunto de 1 elemento.
b. Pruebe que hay exactamente dos relaciones de equivalencia en un conjunto de 2 elementos.
c. ¿Cuántas relaciones de equivalencia hay en un conjunto con 3 elementos? Escrı́balas explı́citamente.
