I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with
$$
T(n) = 4T(n/3)
$$
For all $n > 1$ where $n$ is some power of $3$.
I started out with forward substitution and asserted my assumption that:
$$
T(n) = 4^{\log_3(n)}
$$
At that point I asserted the induction step that I have to prove:
$$
T(3n) = 4^{\log_3(3n)} = 4^n
$$
So I started out with:
$$
T(3n) = 4T(3n/3)
$$
Then I simplified:
$$
T(3n) = 4T(n)
$$
As per my assumption, I substituted $T(n)$.
$$
T(3n) = 4 \cdot 4^{\log_3(n)}
$$
This is where I get stuck, and I was just wondering if someone could point me in the right direction? Thanks!
Best Answer
What was your initial value? You need it for forward substitution, as you are observing a pattern and then proving through induction. Let's assume T(1) = 1.
$$T(3) = 4$$
$$T(9) = 4 \cdot 4 = 4^2 = 16$$
$$T(27) = 4 \cdot 16 = 4^3 = 64$$
So now prove that $T(3^n) = 4^n$. Know that $T(1)=1$, assume that $T(3^n)=4^n$. Then
$$T(3^{n+1}) = 4 T(3^n) = 4 \cdot 4^n = 4^{n+1}$$
So we proved the formula by induction.
We may also solve this equation in closed form directly as follows.
Let $n=3^m$, and
$$T\left(3^m\right) = U_m$$
Then
$$U_m = 4 U_{m-1}$$
which means that
$$U_m = 4^m \, U_0$$
This is the solution for $n$ being a power of $3$. However, we can go further. Substituting $m = \log_3{n}= \log{n}/\log{3}$, we get
$$T(n) = 4^{\log{n}/\log{3}}T(1)$$
or rewriting using $n = e^{\log{n}}$:
$$T(n) = T(1) n^{\log{4}/\log{3}} = T(1) n^{\log_3{4}}$$