The question: solve by recurrence relation using forward substitution and verify by mathematical induction.
$$ \begin{align} &T(n) = 3T(n/3) \quad \text{for $n>1$, $n$ a power of $3$} \\ &T(1) = 2 \\ &T(3) = 3T(1) = 3 * 2 = 6 \\ &T(9) = 3T(3) = 3 * 6 = 18 \\ &T(27) = 3T(9) = 3 * 18 = 54 \\ &T(n) = 2n \\ \end{align} $$
Induction Base: $T(1) = 2 * 1 = 2$
Anyone know if I'm on the right lines, just need a push in the right direction as I am unable to prove:
$$ T(n+1) = 2n+1 $$
You only need to prove it
"for n>1, n a power of 3"so let $n=3^k$ for some integer $k \ge 0\,$.It follows by induction that $\,T\left(3^k\right) = 2 \cdot 3^k\,$ for all $k$:
the base case $k=0$ checks out since $T\left(3^0\right) = T(1) = 2 = 2 \cdot 3^0\,$;
if $T\left(3^k\right)= 2 \cdot 3^k $ then $\;T\left(3^{k+1}\right) = 3 \cdot T\left(3^{k+1} / 3\right) = 3 \cdot T\left(3^k\right) = 3 \cdot 2 \cdot 3^k = 2 \cdot 3^{k+1}\,$.