Inspired by the excellent generatingfunctionology, I am trying to find the (ordinary) generating function for the recurrence describing worst-case runtime for merge sort:
$$ \begin{align*} T_0 &= 0 \\ T_{2n} &= 2\ T_n + n \\ T_{2n+1} &= 2\ T_n + n \end{align*} $$
Applying the transform to get a formal power series and simplifying, we get:
$$ \begin{align*} \sum_{n \ge 0} T_{2n}\ x^n &= \sum_{n \ge 0} \left(2\ T_n + n\right)\ x^n \\ &= 2 \sum_{n \ge 0} T_n\ x^n + \sum_{n \ge 0} n x^n \\ &= 2 \sum_{n \ge 0} T_n\ x^n + \left(\frac{d}{dx}\sum_{n \ge 0} x^{n+1}\right) - \sum_{n\geq 0} x^n \\ \frac{T(\sqrt{x}) + T(-\sqrt{x})}{2} &= 2\ T(x)\ + \frac{x}{(1-x)^2} \end{align*} $$
But I am not sure how to solve for $T(x)$ when square roots are involved. Is there a particular class of functions which model this relationship nicely? If I try to "invert" the recurrence, i.e.:
$$ \begin{align*} T_0 &= 0 \\ T_n &= 2 T_{\lfloor n/2 \rfloor} + n \end{align*} $$
I end up with a similar equation involving $T(x^2)$ instead. I know that $T_n = O(n \, \log n)$, but I'm having trouble using that information as well.