Given the following recurrence:
$$ T(n) = T(n-1) + n^2$$
How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion we pay $n^2$ and we have $n$ steps of recursion therefore having: $n \times n^2 = n^3$.
I would even expect this to be $\Theta(n^3)$, but I can't even prove $O(n^3)$.
I tried with the guess:
$$ T(n) \leq n^3 + n^2 \cdot c_1 + n \cdot c_2 + c_3 $$
but that yields:
$$ T(n) \leq n^3 + n^2 \cdot (3 + c_1) + n \cdot (c_2 - 2c_1 -1) + (c_1 - 1 - c_2 + c_3) $$
which yields:
- $c_1 = c_1 + 3$
- $c_2 = c_2 - 2c_1 - 1$
- $c_3 = c_1 - 1 - c_2 + c_3$
But even from the very first ($c_1 = c_1 + 3$) we find that no $c_1$, $c_2$ or $c_3$ satisfy the equations.
What did I do wrong?