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

Trimestre 2017 Invierno

Entrega: 24 de enero de 2017 en clase.

  1. Demuestra por inducción en n ≥ 0 que 1(1+1) + 2(2+1) + ... + n(n+1) = n(n+1)(n+2)/3.
  2. Demuestra por inducción en n ≥ 0 que 1(1!) + 2(2!) + ... + n(n!) = (n+1)! - 1.
  3. Demuestra por inducción en n ≥ 0 que 20 + 21 + ... + 2n = 2n+1 - 1.
  4. Demuestra por inducción en n ≥ 0 que 1(21) + 2(22) + ... + n(2n) = (n-1)2n+1 + 2.
  5. Demuestra por inducción en n ≥ 0 que A = B, donde:
    1. A = 1/(n+1) + 1/(n+2) + ... + 1/(n+n) y
    2. B = [1/(2(1)-1) - 1/(2(1))] + [1/(2(2)-1) - 1/(2(2))] + ... + [1/(2(n)-1) - 1/(2(n))].
  6. Demuestra por inducción en n ≥ 7 que 3n < n!.
  7. Demuestra por inducción en n ≥ 5 que 2n > n2.
  8. Demuestra por inducción que cualquier entero mayor que 5 se puede escribir como la suma de algunos 2 y algunos 7 (por ejemplo 11 = 2 + 2 + 7).
  9. Demuestra por inducción en n ≥ 0 que F0 + F1 + F2 + ... + Fn = Fn+2 - 1.
  10. Demuestra por inducción en k ≥ 0 que Fn+k = Fk Fn+1 + Fk-1 Fn.
Para las preguntas 9 y 10, recuerda que los números de Fibonacci se definen como F0 = 0, F1 = 1 y Fn = Fn-1 + Fn-2 para toda n ≥ 2.