A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.
Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$
Statement: we wish to prove that $T(n) \le 5 \ n \log n$ for $n \ge 0$
Base case, $n = 0$ and $T(0) \le 0$
$T(0) = 0$
$T(0) \le 0 \log 0$
Holds, since $0 \log 0 = 0$
Inductive step, for $n > 0$
(Inductive Hypothesis is: $T(n) = 5 \ n \log n$)
$T(n) = T(\lceil n/5 \rceil + 36) + n \log n$
$\le 5 \, (\lceil n/5 \rceil + 36) \log (\lceil n/5 \rceil + 36) + n \log n$ by Ind. Hyp.
$\le 5 \, (n/5 + 36) \log (n/5 + 36) + n \log n$ by property of ceiling
$= (n + 180) \log ((n + 180)/5) + n \log n$ by algebra
This is the point where it gets hazy. According to the link, what I should do is say that for all $n \ge 180$, then
$\le (n + n) \log ((n + n)/5) + n \log n$
$= 2n \log (2n/5) + n \log n$
$= 2n \, [\log n + \log (2/5)] + n \log n$
$= 2n \log n + 2n \log (2/5) + n \log n$
$= 3n \log n + kn$ where $k = \log (2/5) * 2$
$\le 5n \log n$
Does this complete the proof? Or am I in error? I still don't understand why I can just set $n \ge 180$ and therefore get rid of the irritating arithmetic within the log.