Consider the following
$$ T(n) = \begin{cases} 0, & \text{for } n=1\\ 2T(n/2) + n, & \text{otherwise} \end{cases} $$
This can be solved via recursion tree or backwards substitution as follows
$$ T(n) = 2T(n/2) + n \\ = 2(2T(n/4)+\frac{n}{2})+n\\ = 4(2T(n/8)+\frac{n}{4})+2n\\ ...\\ =2^kT(n/2^k)+kn $$ For the base case, $k=\log_2(n)$
So, $$ T(n)=n\log_2(n) $$
But I want to solve this using $\mathcal{Z}-$transform or any other more suitable transform it it exists. This is how much I have done
$$ T(n) = 2T(n/2) + n \\ \mathcal{Z}\{T(n)\} = 2\mathcal{Z}\{T(n/2)\} + \mathcal{Z}\{n\}\\ T(z) = 2T(z^2)+\frac{z}{(z-1)^2} $$
$T(z^2)$ and $T(z)$ both are functions of $T(z)$. We can also say them to be $T(z^2)$. I am stuck here
How to proceed after this? Should I take $T(z)-2T(z^2)$ just as $cT(z^2)$ and proceed? Or should I do something else?
First making $n = 2^m$ and then considering
$$ T(2^m) = 2T(2^{m-1})+2^m $$
as
$$ R(m) = 2R(m-1) + 2^m $$
Now you can solve $R(m)$ by using the $\mathcal{Z}$ transform, etc.