I'm having a lot of trouble trying to solve a basic recurrence relation.
$T(n) = 3T(n-5)$ T(x)= 1 for x<= 5
I feel like this problem could be solved by simply plugging in for T(n-5) in terms of T(n-10) and so on, but when I follow this procedure I just end up with another recurrence relation rather than a function purely in terms of 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))$
I get $T(n) = 3^{n-5}T(n-5(n-5))$ . I can't seem to find a formula purely in terms of n. Where am I going wrong?
EDIT: in case it provides some context, I'm supposed to find an answer in theta notation, so I really need to find some function purely of n.
EDIT: After solving, I got $T(N) = 3^{(n-1)/5}$, but I don't feel like this is correct. Could someone verify this for me?
Best Answer
Hint Note that per the recurrence relation, the value of $T(n)$ depends only on $T(n - 5)$, so, e.g., the subsequence $S := [T(1), T(6), T(11), \ldots]$ can be determined without finding any of the intermediate values, $T(2), T(3),$ etc. Computing gives that this subsequence is $[1, 3, 9, \ldots]$---can you find an explicit formula for $S$?