# 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

## 1 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$?

• im guessing the formula for S would be 3^n, but is that a solution to the original relation? If the sequence is what you wrote earlier (1, 1,1 ,1 1, 3, 3, 3, 3, 3, 9, 9...) then I would need some way to computer 3^n when 6 <= n <= 10. I tried 3^(n-5) but that obviously wouldn't work. Sep 8 '15 at 0:42
• sorry if it's something super obvious. I don't know why I'm not arriving to the same conclusion. Sep 8 '15 at 0:42
• so my final answer for T(n) = 3^((n-1)/5). Does this seem reasonable? It doesn't seem to work for the base case so did I make a mistake? Sep 8 '15 at 1:42
• 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
• Ah that's what I thought. I added that in my answer but I didn't know if it was valid considering I'm looking for a theta value. Thanks Sep 8 '15 at 2:16