Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition $T(1) = 1$ for recurrence (4.19) without adjusting the boundary conditions for the inductive proof.

Let us assume $T(n) \le c n \lg n + 1$ for all $n \ge n_0$, where $c$ and $n_0$ are positive constants.

The last step holds as long as $c \ge 1$.

Hence, at the boundary, $T(n) \le c \cdot 1 \cdot \lg 1 + 1 = 1$.