Solving recurrences with the Substitution Method

To give a direct answer to your question it comes from the guess in step $(a)$.

$T(n) = n \log_2 (n) + n$ is the guess you made in step $(a)$. Using that replace $n = \frac{n}{2}$, $T(\frac{n}{2}) = \frac{n}{2} \log_2 (\frac{n}{2}) + \frac{n}{2}$.

$T(\frac{n}{2}) = \frac{n}{2} (\log_2 (n) - \log_2(2)) + \frac{n}{2} = \frac{n}{2} \log_2 (n) - \frac{n}{2} + \frac{n}{2} = \frac{n}{2} \log_2 (n)$

Hence, $T(n) = 2 T(\frac{n}{2}) + n = 2 \frac{n}{2} \log_2 (n) + n = n \log_2 (n) + n$

While solving some recurrences it is good to recognize some nice things about the recurrence you are actually solving. For instance in this recurrence, notice that at each step you are dividing $n$ by $2$. So strictly speaking through the recurrence you can only obtain $T(2^m)$ where $m \in \mathbb{N}$. For instance, $T(3)$ cannot be obtained using this recurrence. However, such recurrences come up when you do certain things, when $n$ is really large, recursively using say a binary tree. When $n$ is really large you are interested mainly in how the solution behaves in an asymptotic sense and not the precise expression for the solution. In such cases, you assume that $n=2^m$ for the simplicity of calculations and the cost for all $n$ (even when $n$ is not a power of $2$) can be shown to obey the solution, obtained by the assuming $n=2^m$, in an asymptotic sense.

If you were to rewrite the recurrence in terms of $m$, and call $T(2^m) = S(m)$, then we would get

$S(m) = 2 S(m-1) + 2^m$ since $\frac{n}{2} = 2^{m-1}$.

$S(m-1) = 2 S(m-2) + 2^{m-1}$.

$S(m) = 4 S(m-2) + 2^m + 2^m$ and so on (hidden induction here) to get

$S(m) = 2^m S(0) + 2^m + 2^m + \cdots + 2^m + 2^m = m 2^m + 2^m$.

Hence $T(n) = n \log_2(n) + n$ since $n = 2^m$ i.e. $m = \log_2(n)$

As they say, it is a guess. If (as in a) $T(n)=n lg n + n$ you just substitute to get the one you ask "To here". So the real question is whether induction is justified. The point is that if the expression for T is valid up to n it is valid up to 2n (and you need to explain in this case what happens for odd $n$) then it is valid for all $n$.