Tarea 1 de Análisis de Algoritmos

Trimestre 2007 Primavera
Entrega: 17 de mayo de 2007 en clase.

1. Demuestre por inducción que 1² + 3² + ... + (2n+1)² = (n+1)(2n+1)(2n+3)/3 para toda n >= 0.
2. Demuestre por inducción que 3ⁿ < n! para toda n >= 7.
3. Demuestre por inducción que si sólo se tienen monedas de 2 y 7 pesos entonces se puede pagar cualquier cantidad n >= 6.
4. Demuestre que el siguiente algoritmo para calcular y^z es correcto:
   
   x := 1
   mientras z > 0 haz
   
   si z es impar entonces x := xy
   z := z/2 (parte entera)
   y := y²
   
   regresa x
   
5. Para cada una de las siguientes parejas de funciones f(n) y g(n) se tiene que ya sea f(n) es O(g(n)) ó g(n) es O(f(n)) pero no ambas. Diga qué es lo correcto y demuéstrelo:
1. f(n) = n + log n, g(n) = n^3/2.
2. f(n) = n + log n, g(n) = n^1/2.