DiscretaFiis

Ejercicios
Matem´atica Discreta
Martes, 20 de marzo del 2015

1. Determine el n´umero de pares ordenados (A, B), donde A ⊂ B{1, 2, ·· · , n}.
2. Muestre que un n´umero
√ natutal n ≥ 1 tiene un n´umero impar de divisores (incluido el 1 y e´ l
mismo) si, y solo si nes entero.
3.

(a) Pruebe ls f´ormula
r
r+1
r+2
n
+
+
+ ··· +
r
r
r
r

=

n+1
.
r+1

por inducci´on sobre n (para r arbitrariofijo).
(b) Pruebe la f´ormula anterior con otro m´etodo.
4. Calcule
n

(a)
k=1
n

(b)
k=0

k 1
m k
k
k
m

5. Pruebe que
m

k=0

m
k

n+km

m

=
k=0

n
k

m
2k
k

6. ¿Cu´antas aplicacioines f : {1, 2, · · · , n} −→ {1, 2, · · · , n} existen que sean mon´otonas; es
decir,para n < m tenemos f (n) < f (m)?
7. Encuentre funciones positivas y no decrecientes f, g : N −→ R tales que no cumplan ni
f (n) =O(g(n)) ni g(n) = O(f (n)). Una funci´on f es no decreciente si n ≤ m esto
implica que f (n) ≤ g(m).
8. ¿Cu´al es el significado delas siguientes notaciones f (n) = O(1), g(n) = Ω(1), h(n) =
nO(1) ? Justifique su respuesta.
9. Compruebe si es verdadero o falso,justificando su respuesta, si f1 (n) = O(g1 (n)) y f2 (n) =
O(g2 (n)) entonces se tiene f1 (n)+f2 (n) = O(g1 (n)+g2 (n)) y f1 (n)f2 (n) =O(g1 (n)g2 (n)).
10. Use inducci´on matem´atica para probar que
√
√
1
1
1
2 n + 1 − 2 < 1 + √ + √ + · · · + √ ≤ 2 n − 1.
n
2
3