I am learning substitution method for solving recurrence and there is the recurrence $T(n−1)+n$ and we need prove that it is $O(n^2)$ and we guess that $T(n) \leq cn^2$.
So we solve for $$T(n) \leq c(n-1)^2 + n$$ $$ T(n) = cn^2 - 2cn + c +n$$ $$ T(n) = cn^2 + n(1-2c) + c$$
I follow it until above, but I am completely lost at how the final answer is $$ T(n) \leq cn^2 $$ where the last step holds for $c > \frac{1}{2}$. I understand that it is saying that if $ T(n) = cn^2 + n(1-2c) + c$ then it is also $ T(n) \leq cn^2 $. But I don't understand how the inequality $c > \frac{1}{2}$n was found?
$$T(n) = c(n-1)^2 + n \leqslant cn^2+n^2= (c+1)n^2 \in O(n^2)$$ Formulation can be following: as $T(n)= c(n-1)^2 + n$, then we can find such constant $\exists A=c+1$, that $T(n) \leqslant An^2$, so $T(n)$ is $O(n^2)$.