its been a while since I have done proofs and am struggling on a question:
Let $T(n)$ be defined recursively as follows: $T(1)=c$ and $T(n)=3T(n/3)+c, \forall n\geqslant 3$, where $c$ is some arbitrary positive constant and $n=3^k$ for some non-negative integer $k$. Prove by induction on $k$ that $T(n)=(3c)/(2) n - c/2$.
So far I have been able to break it down to the following:
- Base Case = $T(1) = c$
- Recursive Case = $T(n)=3T(n/3)+c$
- Since $n=3^k$ this makes the recursive case: $T(3^k) = 3T(3^{k-1})+c$
Beyond that I am struggling at where to start. I know I need to prove it for the lowest possible value i.i. $k=1$, which I think gives me:
$T(3)=3T(3/3)+c$
$= 3T(1)+c = 4c$
I don't think this is right though and don't really know why.
Any help is appreciated.
You are virtually there. The induction is really an induction on $k$ starting at $0$, to prove $T(n) = (3c/2)\cdot n - c/2$ where $n = 3^k$: For the base case:
$$T(3^0) = T(1) = c = (3c/2)\cdot 3^0 - c/2$$
For the inductive step, the inductive hypothesis is:
$$T(3^k) = (3c/2)\cdot 3^k - c/2$$
and using this and the recursive definition, you get:
$$T(3^{k+1}) = 3T(3^k) + c = 3\left[(3c/2)\cdot 3^k - c/2\right] + c= (3c/2)\cdot 3^{k+1} - c/2$$
which completes the inductive proof