Tarea 1 de Análisis y Diseño de Algoritmos

Trimestre 2013 Otoño
Entrega: 2 de septiembre de 2013 en clase.

  1. [1 punto] Demuestra por inducción que si n >= 1 entonces 12 + 22 + 32 + ... + n2 = n(n+1)(2n+1)/6.
  2. [1 punto] Demuestra por inducción que si n >= 0 entonces 12 + 32 + 52 + ... + (2n+1)2 = (n+1)(2n+1)(2n+3)/3.
  3. [1 punto] Demuestra por inducción que si n >= 1 entonces 1/(1*2) + 1/(2*3) + 1/(3*4) + ... + 1/(n*(n+1)) = n/(n+1).
  4. [1 punto] Demuestra que el siguiente algoritmo iterativo para calcular la exponenciación yz es correcto:
    potencia(y, z)
    1. x := 1
    2. mientras z > 0
      1. x := x*y
      2. z := z-1
    3. regresa x
  5. [1 punto] Demuestra que el siguiente algoritmo recursivo para calcular la exponenciación yz es correcto:
    potencia(y, z)
    1. si z = 0 entonces regresa 1
    2. si z es impar entonces regresa potencia(y2, z/2)*y
    3. en caso contrario regresa potencia(y2, z/2)
    Debes suponer que la división z/2 regresa sólo la parte entera de la división.