Why do I need a base case for n=3 when solving a d&c recurrence?

Question

I was reading CLRS' book on how to use the substitution method to solve recurrences, where they have the following example:

$T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ where $T(1) = 1$

They assume that $T(n) = O(n \log n)$ and go on to prove it by using induction.

I understand the inductive step, but I do not understand how they find the base case.

For $n=1$ we have $T(1) \leq c1 \log 1 = 0$, which is wrong because $T(1) = 1$. So we can not use $T(1)$ as a base case.

For $n=2$ we have $T(2) = 2T(1) + 2 = 4$, so $4 \leq c2 \log2$. The last inequality holds for every $c \geq 2$.

In the book they write that we also need $n=3$ to be the base case. However, they do not really explain why. Why isn't $n=2$ sufficient?

Answer 1

They do not want $T(1)$ to occur as a base case as it causes troubles. $T(3)$ depends on $T(1)$, so if they didn't take $T(3)$ as a base case in addition to taking $T(2)$ as one, they'd run into trouble when applying the inductive step to $T(3)$ as the hypothesis does not hold for $T(\lfloor{\frac{3}{2}}\rfloor)=T(1)$.