I am trying to find the solution for the recurrence equation using substitution :
$$tn=3\cdot t(n/2)+n\quad \text{ where } \quad t1=1/2$$
for $n >1$, $n$ a power of $2$.
I am stuck at
$$tn = 3^{\lg n} + n \cdot\sum\limits_{i=1}^{\lg n-1} \left(\frac{3}{2}\right)^{\lg n - i} $$
I checked this question, but still not able to figure out how to solve the above equation.
To me it's easier not to start with a version with logarithms.
Writing down the first few terms,
$t_1 = \frac{1}{2}$
$t_2 = \frac{3}{2} + 2 $
$t_4 = 3\cdot (\frac{3}{2} +2) + 4$
$t_8 = 3\cdot ( 3\cdot (\frac{3}{2} +2) + 4 ) + 8$
etc.
it becomes clear that we can write this in closed form as $t_{2^n} = \frac{3^n}{2} + \sum_{i=0}^{n-1}3^i 2^{n-i} = \frac{3^n}{2} + 2^n\sum_{i=0}^{n-1} (\frac{3}{2})^i = \frac{3^n}{2} + 2^n \cdot\frac{(\frac{3}{2})^n -1}{\frac{3}{2}-1} = \frac{3^n}{2}+2\cdot 3^n-2^{n+1}$
$ =\frac{5}{2}\cdot 3^n - 2^{n+1}$
We could also write this with logarithms as
$t_n = \frac{5}{2} \cdot 3^{log_2(n)} - 2n = \frac{5}{2}\cdot n^{log_2(3)}-2n$