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.
At the boundary, \(T(1) \le c \cdot 1 \cdot \lg 1 + 1 = 1\) which does not contradict the given boundary condition.
Now, we need to show the assumption holds.
\[\begin {aligned} T(n) & \le 2c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + 1 + n \\ & \le cn \lg (n/2) + 1 + n \\ & = cn \lg n - cn \lg 2 + 1 + n \\ & = cn \lg n + 1 - (c - 1)n \\ & \le cn \lg n + 1 \end {aligned}\]The last step holds as long as \((c - 1)n \ge 0\).
And this is possible with \(c \ge 1\) and \(n \ge n_0 = 1\).
Can we pick XXX
As a reader has asked in the comments section, can we assume our inductive hypothesis to be \(n \lg (n + 1)\)? As mentioned in above note, it is within the same asymptotic limit, but it will make it difficult to prove that using substitution method. Note that with this assumption, we are essentially assuming \(c = 1\).
Let’s try and see for ourselves.
\[\begin {aligned} T(n) & \le 2 \lfloor n/2 \rfloor \lg (\lfloor n/2 \rfloor + 1) + n \\ & \le n \lg (n/2 + 1) + n \\ & = n \lg ((n + 2 ) / 2) + n \\ & = n \lg (n + 2) - n \lg 2 + n \\ & = n \lg (n + 2) - n + n \\ & = n \lg (n + 2) \end {aligned}\]We cannot really prove our assumption from above, without modifying our guess by adding/subtracting some lower-order terms, in which case our assumption will change.