Tarea 1 de Análisis de Algoritmos (2006 Otoño)

Fecha de entrega: 10 de octubre de 2006 en clase

1. Demuestre por inducción en n que 1*2 + 2*3 + 3*4 + ... + (n-1)*n + n*(n+1) = n*(n+1)*(n+2)/3 para toda n >= 1.
2. Demuestre por inducción en n que 2ⁿ > n² para toda n >= 5.
3. ¿Cuál es el menor entero k tal que cualquier marcador n >= k se puede lograr en un juego de futbol americano usando solamente anotaciones de 3 y 7 puntos? Demuestre que su respuesta es correcta.
4. Demuestre que si f(n) = 1000n y g(n) = 2ⁿ entonces f(n) es O(g(n)).
5. Demuestre que si f(n) = 2ⁿ y g(n) = n! entonces f(n) es O(g(n)).