Given:
$$
T(n) = \begin{cases}
4, & n = 1\\
T(n - 1) + 3n, & n > 1\\
\end{cases}
$$
I was trying to prove that $T(n) = O(n^2)$ using the substitution method.
I guess that the solution is $O(n^2)$, and I have to prove by induction that $\exists c > 0, n_0 \ni \forall n \ge n_0, \space T(n) = cn^2$.
So, I started like this:
$$
T(n) \le c(n - 1)^2 + 3n = cn^2 - 2cn + c +3n = cn^2 -n(2c \space - \space 3) + c
$$
Since I am trying to prove that $cn^2 - n(2c - 3) + c = O(n^2)$, I continued like this:
$$
cn^2 - n(2c - 3) + c \le cn^2\\
-n(2c - 3) + c \le 0\\
n(2c - 3) \ge c\\
n \ge \frac{c}{2c - 3}
$$
This result means that $T(n) = O(n^2), \space \space \forall n\ge \frac{c}{2c-3}$.
This proof is correct, because the last condition doesn't "force" c to grow with n, but n has to be greater than some fixed constant, is that correct?
For the sake of the argument, if I had $\frac{c}{2c-3} \ge n$, the proof would have failed because this condition "forces" c to grow with n, right?
Note that we don't generally use induction to find $O$ bounds, and the reason is trivial, you have that $T(n) \le c n^2$ for $n \ge n_0$ only, but for $n < n_0$, you dont have $T(n) \le c n^2$, so an induction argument won't work.
The way you find O bounds for functions specified by recursion is by unfolding the recursion (here you can use induction) or alternatively using Master Theorem.