I am trying to solve a recurrence using substitution method (I am asking for help/confirmation about this solving method, so don't answer with a solution developed by iteration method or something else).
I want to precise that I have just started studying recurrence relations, so I am asking for confirmation of my work.
Given:
$$
T(n) = \begin{cases}
1 & n = 1
\\
T(n - 1) + n^2 & n \gt 1
\end{cases}
$$
I guess that $T(n) = O(n^3)$, so:
$$
T(n) = T(n \space - \space 1) + n^2 \le c(n - 1)^3 + n^2\\
c(n - 1)^3 + n^2 = cn^3 - 3cn^2 + 3cn - c + n^2
$$
then I continued like this:
$$
cn^3 - 3cn^2 + 3cn - c + n^2 \le cn^3\\
3cn^2 - 3cn + c - n^2 \ge 0\\
$$
from now on, this is the part about I am not sure if I did it right:
$$
n(3cn - 3c - n) \ge -c\\
3cn - 3c - n \ge -\frac{c}{n}\\
n - 3c \ge -\frac{3c^2 - c}{n}\\
n \ge\ -\frac{3c^2 - c}{n} + 3c
$$
Now, I am not sure if i did that right.
I know that this recurrence is a $O(n^3)$, but I want to know if my proof is true.
I want to say that this isn't a homework or something like that, it's a simple exercise that came up to my mind.
EDIT:
Let's notice that:
$$
3cn^2 - 3cn + c - n^2 = n^2(3c - 1) - 3cn + c \ge 0
$$
so, all I need to do is to solve this quadratic inequality in order to find for which c values is verified.
Now, I have to calculate the discriminant to check if this inequality has solutions, so:
$$
(-3c)^2 - 4(3c - 1)(c) = 9c^2 - 12c^2 - 4c = -3c^2 - 4c = c(3c + 4)
$$
Only when the discriminant is greater than zero, the inequality has solutions, and in this case: $$ 3c + 4 > 0\\ 3c > -4\\ c > -\frac{4}{3} $$
From this result, it's proven that $T(n) = O(n^3), \space \forall c > -\frac{4}{3}$
I thought about this proof, is it wrong or did I missed something?
To solve the recurrence exactly, you need to assume a more general ansatz: $$T(n) = An^3+Bn^2+Cn.$$ Substitution yields: $$An^3+Bn^2+Cn = A(n-1)^3+B(n-1)^2+C(n-1) + n^2.$$ If we let $n = 1,2,3$, we get the system of equations $$A+B+C = 1,$$ $$7A+3B+C = 4,$$ $$19A+5B+C = 9.$$