Big-O proof for a recurrence relation? This question is fairly specific in the manner of steps taken to solve the problem.

Given 
$T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$.

So the steps were as follows. We want to prove that $T(n) \le cn^2$.

$$\begin{align*}
T(n)&amp;=2T(2n/3)+O(n)  \\
&amp;\leq 2c(2n/3)^2+an\\
&amp;\leq (8/9)(cn^2)+an
\end{align*}$$
and then my prof went on to do:

$$T(n) \leq cn^2+(an-(1/9)cn^2)\,,$$
which comes out to:

$$T(n)\leq cn^2 \text{ for any }c &gt;= 9a\,.$$

My question is, how were they able to switch from 8/9 to 1/9 while introducing a new term? Is this allowed? She never explained, this was just in her solutions.
As you pointed out, the reason for splitting the term into two pieces is to be able to cancel the $an$ term. If we go directly from $(8/9)cn^2 + an \leq cn^2 + an$, then we get stuck as we cannot do anything with the $an$ term. By splitting it in the way described, this allows the $(1/9)cn^2$ to be larger than $an$ when $c \geq 9a$, which then gives you the desired result since $an - (1/9)cn^2 \leq 0$ for such values of $c$.