What kind of series / recursion is this? I'm trying to find the explicit solution / sum of first n elements for the following sequence:
d(2) = 2
d(n) = d(n/2) + n*log2(n)

Can you help me to find out what kind of recursion is this and how can I find the explicit solution and the sum of the first n elements?
I've calculated the first few elements, and it goes like this:
2 + 8 + 24 + 64 + ....

(I've arrived here by trying to calculate the asymptotic running time of the bitonic sorting algorithm on a ring-connected parallel architecture, and this is the last part but I'm stuck with this equation)
 A: Since the recurrence is only defined when $n$ is a power of 2, we'll let $n=2^k$ for an integer $k\ge 1$. For ease of writing, we'll denote $\log_2 x\text{ by }\lg x$ so your recurrence may be written as
$$
d(2^k)=\begin{cases}
          2 & \text{if }k=1 \\
          d(2^{k-1})+k\:2^k & \text{if }k>1
       \end{cases}
$$
Now we can repeatedly apply this definition to the terms in brackets:
$$
\begin{align}
d(2^k) &= [d(2^{k-1})]+k\:2^k \\
       &= [d(2^{k-2})+(k-1)2^{k-1}] + k\:2^k =[d(2^{k-2})]+(k-1)2^{k-1} + k\:2^k\\
       &= [d(2^{k-3})]+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k\\
       &= [d(2^{k-4})]+(k-3)2^{k-3}+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k
\end{align}
$$
and eventually wind up with
$$
d(2^k)=(1)2^1+(2)2^2+(3)2^3+\cdots+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k
$$
There's a closed form for this (see the notes below), but if you happen not to know it, we can still get an upper bound by slightly rewriting is as
$$
d(2^k)=(k-(k-1))2^1+(k-(k-1))2^2+\cdots+(k-1)2^{k-1} + k\:2^k
$$
and then separating positive and negative terms:
$$
\begin{align}
d(2^k)&=[k\:2^1+k\:2^2+\cdots+k\:2^k]-[(k-1)2^1+(k-2)2^2+\cdots + (1)2^{k-1}]\\
      &\le k\:2^1+k\:2^2+\cdots+k\:2^k \\
      &=2k(1+2+4+\cdots 2^{k-1})\\
      &=2k(2^k-1)
\end{align}
$$
now using the fact that $n=2^k$ (and hence $k=\lg n)$ we've shown that
$$
d(n)\le (2\lg n)(n-1)
$$
and we finally have our (expected) asymptotic upper bound
$$
d(n)=O(n\lg n)
$$

Some additional notes 


*

*In your last comment you said that $n\lg n$ works "kind of like" an $n^k$. This is intuitively right, but strictly speaking I suspect that your version of the Master Theorem doesn't apply to terms that aren't polynomials.

*I mentioned that there is a closed form for the sum. It follows from the fact that
$$
x+2x^2+3x^3+\cdots+kx^k=\frac{x}{(x-1)^2}(kx^{k+1}-(k+1)x^k+1)
$$
which you can get from the sum of the geometric series $1+x+x^2+\cdots + x^k$ by differentiating. Thus we have the exact solution $d(n)=2n(\lg n-1)+2$ which gives us the stronger asymptotic estimate $d(n)=\Theta(n\lg n)$.

