3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The first terms of the sequence are: $1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 9, 9, 9, 9, 9, 27, \ldots$. $\endgroup$ Sep 7 '15 at 23:59
  • $\begingroup$ 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 $\endgroup$ Sep 8 '15 at 0:01
0
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Sep 8 '15 at 0:42
  • $\begingroup$ sorry if it's something super obvious. I don't know why I'm not arriving to the same conclusion. $\endgroup$ Sep 8 '15 at 0:42
  • $\begingroup$ 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? $\endgroup$ Sep 8 '15 at 1:42
  • $\begingroup$ 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$. $\endgroup$ Sep 8 '15 at 1:56
  • $\begingroup$ 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 $\endgroup$ Sep 8 '15 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.