Recurrence equation of $ T(n) = T(n/2 ) + dn\log_2(n)$ I have the following equation:
$$T(n) = T\left({n \over 2}\right) + d  n  \log_2 n$$
A little investigation:
$T(2^1) = 1 + 2d$
$T(2^2) = T(2^1) + 2^2d\times 2 = 1 + 10d$
$T(2^3) = T(2^2) + 2^3d\times 3 = 1+34d$
I know the next one is by adding $2^nnd$ but I fail to see a pattern so I couldn't conclude $T(n)$ in a generic form. 
Our teacher won't allow us to use the master theorem but instruct us to use a little investigation like what I did above, prove by induction afterwards.
Would someone help me? Thanks.
 A: We can solve  another closely related recurrence that  admits an exact
solution and makes it possible to get precise bounds.  Suppose we have
$T(0)=0$ and $T(1)=1$ and for $n\ge 2$
$$T(n) = T(\lfloor n/2\rfloor) + 
q\times n\times\lfloor \log_2 n\rfloor.$$
Furthermore let the base two representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Then we  can unroll the  recurrence to obtain the  following exact
formula for $n\ge 2$
$$T(n) = 1 + q\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor - j)
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
This follows more or less by inspection.

Now to get an upper bound consider a string of one digits, which gives
$$T(n) \le
1 + q\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor - j)
\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}
\\= 1 +
q\left(
4 \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
- 4 \times 2^{\lfloor \log_2 n \rfloor}
- \frac{1}{2} (\lfloor \log_2 n \rfloor)^2
- \frac{1}{2} \lfloor \log_2 n \rfloor
+ 4\right).$$

For a lower bound consider a  one followed by a string of zero digits,
giving
$$T(n) \ge
1 + q\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor - j)
2^{\lfloor \log_2 n \rfloor-j}
\\ =
1 + q\left(
2 \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
- 2 \times 2^{\lfloor \log_2 n \rfloor}
+ 2
\right).$$

Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\color{#006}{q \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
\in \Theta\left(\log_2 n \times 2^{\log_2 n}\right) 
= \Theta\left(\log n \times n\right)}.$$
These are in agreement with what the Master theorem would produce.

Here is another computation in the same spirit: 
MSE link.
A: Proof by induction: Assume that, for some $n\geqslant1$ and some $c\gt0$, property $H_n(c)$ holds, where $$H_n(c):\qquad\forall k\leqslant n,\ T(k)\leqslant ck\log_2k.$$ Then $\log_2\left(\tfrac12(n+1)\right)\leqslant\log_2\left(n+1\right)$ and $n\log_2n\leqslant(n+1)\log_2(n+1)$ hence the upper bound $$T(n+1)= T(\tfrac12(n+1))+dn\log_2n\leqslant\tfrac12c(n+1)\log_2\left(\tfrac12(n+1)\right)+d(n+1)\log_2(n+1),$$ implies that $$T(n+1)\leqslant \left(\tfrac12c+d\right)(n+1)\log_2(n+1),$$
thus, $H_{n+1}(c)$ holds provided $$\tfrac12c+d\leqslant c.$$ Surely you can finish this.
