# Solving recurrence relation using unrolling

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?

• The first terms of the sequence are: $1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 9, 9, 9, 9, 9, 27, \ldots$. Sep 7 '15 at 23:59
• Right, but I guess I'm missing a crucial concept because how am I supposed to convert that into a function of n without recursion Sep 8 '15 at 0:01

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$?
• You're very close, but we can see that we only want to raise $3$ to integer powers, namely, and we can denote rounding a number $a$ down to the nearest integer by $\lfloor a \rfloor$. Sep 8 '15 at 1:56