Tarea 1 de Diseño de Algoritmos
Trimestre 2008 Primavera
Entrega: 30 de junio de 2008 (en clase)
Problema 1 (2 puntos):
Demuestre por inducción en n que 1*1! + 2*2! + 3*3! + ... + n*n!
= (n+1)! - 1 para toda n >= 1.
Problema 2 (2 puntos):
¿Qué es lo que está mal con la siguiente "prueba"
por inducción? Demostraremos que 6n = 0 para toda n >= 0.
Claramente, si n = 0 entonces 6n = 0. Ahora suponga que n > 0 y sea
n = a+b. Por la hipótesis de inducción 6a = 0 y 6b = 0.
Por lo tanto 6n = 6(a+b) = 6a + 6b = 0 + 0 = 0.
Problema 3 (3 puntos):
Demuestre por inducción en n que 1/(1*2) + 1/(2*3) + 1/(3*4) +
... + 1/(n(n+1)) = n/(n+1) para toda n >= 1.
Problema 4 (3 puntos):
Demuestre por inducción que la representación binaria de
n tiene exactamente int(log2 n) + 1 bits para toda n >=
1, donde int(x) es la parte entera de x.