Resolución de relaciones de recurrencia mediante desenrollado

Question

Estoy teniendo muchos problemas intentando resolver una relación de recurrencia básica.

$T(n) = 3T(n-5)$ T(x)= 1 para x<= 5

Me parece que este problema podría resolverse simplemente introduciendo T(n-5) en términos de T(n-10) y así sucesivamente, pero cuando sigo este procedimiento sólo obtengo otra relación de recurrencia en lugar de una función puramente en términos de n.

$T(n) = 3T(n-5)$

$T(n-5) = 3T(n-10)$

$T(n-10) = 3T(n-15)$

$T(n) = 3(3(3(T(n-15)) = 3^{n-5}T(n-5(n-5))$

Recibo $T(n) = 3^{n-5}T(n-5(n-5))$ . No consigo encontrar una fórmula puramente en términos de n. ¿En qué me equivoco?

EDIT: en caso de que proporcione algún contexto, se supone que debo encontrar una respuesta en notación theta, por lo que realmente necesito encontrar alguna función puramente de n.

EDIT: Después de resolver, tengo $T(N) = 3^{(n-1)/5}$ pero no me parece correcto. ¿Podría alguien verificarlo?

Answer 1

Sugerencia Obsérvese que, según la relación de recurrencia, el valor de $T(n)$ depende únicamente de $T(n - 5)$ por lo que, por ejemplo, la subsecuencia $S := [T(1), T(6), T(11), \ldots]$ puede determinarse sin encontrar ninguno de los valores intermedios, $T(2), T(3),$ etc. El cálculo da que esta subsecuencia es $[1, 3, 9, \ldots]$ ---¿Puede encontrar una fórmula explícita para $S$ ?