0

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

tpvasconcelos
  • 242
Peter Wilson
  • 1

1 Answers1

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}\,$.

dxiv
  • 76,497