Help with Recurrence relations forward substitution and progression

Question

I have seen a few questions regarding this topic. I have been unable to find one that could help me with analyzing the progression.

My question :solve by recurrence relation using forward substitution and verify by mathematical induction.

T(n) = 3T(n/4) for n>1, n a power of 4

T(1) = 3

What i have so far:

T(4) = 3T(4/4) = 3T(1) = 3

T(16) = 3T(16/4) = 3T(4) = 12

T(64) = 3T(64/4) = 3T(16) = 48

T(256) = 3T(256/4) = 3T(64) =192

My Problem: i can't find a way of relating this progression to the problem size n. Nothing jumps out or is obvious to me.

thanks in advance.

Answer 1

Perhaps the problem is that the calculation is slightly wrong.

You should have $$T(4)=3T(1)=3\color{red}{\times 3}=9$$ Similarly we should have

$$T(16)=3T(4)=3\color{red}{\times 9}=27$$

Try rewriting all of these and see if anything now jumps out at you. If you still have trouble seeing it, try writing in terms of powers of $4$ and powers of $3$.

Answer 2

For every non-negative integer $n$ we have $T(4^n)=3^{n+1}$ this can be shown by induction on $n$. For $n=0$ the we have $T(4^0)=3^1$ as we want. Now suppose that you already proved the statement for some natural number $n$, for $n+1$ we have $$ T(4^{n+1})=3T(4^n)=3.3^{n+1}=3^{n+2} $$ Which this completes the induction step.