To prove $T(n) = \Theta(n^2)$ : $$ T(n)\le\left\{\begin{array}{ll} c_1 & n\le 1 \\ \max_{1\le i \le n}(T(i) + T(n-1-i)) + c_2n & n>1 \end{array}\right. $$
I think it is necessary to simultaneously prove $T(n) = O(n^2)$ and $T(n) = \Omega(n^2)$ .
But I don't have any clue about proving $T(n) = \Omega(n^2)$, could you help me? Or there may be any other methods?