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.

Recall that (4.19) refers to \(T(n) = 2T(\lfloor n/2 \rfloor) + n\). Our solution of \(T(n) \leq cn \lg n\) at the boundary condition yields \(T(1) \leq c \cdot \lg 1 = 0\) which certainly does not equal \(1\).

Let us modify our guess to be \(T(n) \leq cn \lg n + n\). Substituting this into the recurrence yields

\[\begin{split} T(n) & \leq 2(c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + \lfloor n/2 \rfloor) + n \\ & \leq cn \lg (n/2) + 2(n/2) + n \\ & = cn \lg n - cn \lg 2n + n \\ & = cn \lg n - cn + 2n \\ & \leq cn \lg n + n \\ \end{split}\]

Where the last step \(cn \lg n - cn + 2n \leq cn \lg n + n\) holds as long as \(c \geq 1\). At the boundary condition, this evaluates to \(T(1) \leq cn \lg n + n = c \cdot 1 \cdot \lg 1 + 1 = 0 + 1 = 1\).