Recurrence relations by forward substitution help

Question

My question is to solve the following using recurrence relation forward substitution then verify using mathematical substitution:

• $T(n) = 2T(\frac{n}{3})$ for $n > 1$, where $n$ is a power of $3$
• $T(1) = 3$

I'm not sure where to start as I'm used to using $T(1) = 3$

Thank you in advance

Answer 1

The value of $T(1)$ need not worry us very much. Suppose that $T(1)=a$.

Then $T(3)=2T(3/3)=2T(1)=2a$.

Similarly, $T(9)=2T(9/3)=4a$, and $T(27)=2T(9)=8a$, and so on.

So in general $T(3^n)=2^n a$. In your particular example, you have $a=3$. So $T(3^n)=(3)(2^n)$.