Argue that the solution to the recurrence $T(n) = T(n/3) + T(2n/3) + cn$, where c is a constant, is $\Omega(n \lg n)$ by appealing to a recursion tree.

This recurrence is the same one used in the chapter text to show the upper bound. We can easily tweak the proof for the lower bound.