Relación de recurrencia Tallas de tareas

Question

Aquí está la pregunta:
Resuelva la recurrencia obteniendo un theta unido para t (n) dado que t (1) = theta (1).

T(n) = n + T(n-3)

Intento de solución:

T(n) = T(n-6) + (n-3) + n  

= T(n-9) + (n-6) + (n-3) + n  

= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n]

= T(1) + [0 + 3 + 6 + ... + n]

= theta(1) = 3[1 + 2 + 3 + ... + n/3]

= theta(1) + [(n/3)(n/3 + 1)]/2

= theta(1) + (n^2+3n)/6

Cuando verifico dos veces para ver si la solución se ajusta a la recurrencia, no funciona.

Answer 1

El problema era que estaba obteniendo la suma equivocada. No comienza en 0, ya que su última función T fue t (n-(n-1)), lo que significa que la anterior era t (n-4)). Entonces la suma comienza a las 4 y sube hasta n.

Si no sabe cómo encontrar la suma de esto, le sugiero que vea algunas de las pruebas de la fórmula de suma. Así es como se ve la solución.

T(n) = T(n-3) + n  

= T(n-6) + (n-3) + n  

= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n]

= T(1) + [4 + 7 + ... + n]

= theta(1) + (4 + n) * (n - 1)/6