Closed form for the recurrence T(n) = T(n-1) + n²

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?

If $T(n)$ is $O(n^3)$, then with a coefficient to $n^3$:

$$
T(n) \leq n^3 c_3 + n^2 c_2 + n c_1 + c_0
$$
So, expanding $T(n+1)$:
$$\begin{align*}
T(n + 1) &\leq (n + 1)^3 c_3 + (n + 1)^2 c_2 + (n + 1) c_1 + c_0 \\
T(n) + (n + 1)^2 &\leq n^3 c_3 + 3n^2 c_3 + 3n c_3 + c_3 + n^2 c_2 + 2n c_2 + c_2 + n c_1 + c_1 + c_0\end{align*} $$

Leading us to:

$$
T(n) \leq n^3 c_3 + n^2 (3c_3 + c_2 - 1) + n (3c_3 + 2c_2 + c_1 - 2) + c_3 + c_2 + c_1 + c_0 - 1
$$

Therefore:

• $ c_3 = c_3 $

• $ c_2 = 3c_3 + c_2 - 1 $

• $ c_1 = 3c_3 + 2c_2 + c_1 - 2 $

• $ c_0 = c_3 + c_2 + c_1 + c_0 - 1$

Solving:

$$\begin{align}
c_3 &= 1/3 \\
c_2 &= 1/2 \\
c_1 &= 1/6
\end{align} \\
T(n) \leq n^3/3 + n^2/2 + n/6 + c_0 = \frac{n(n + 1)(2n + 1)}{6} + c_0
$$

StackExchange Computer Science Q#44311, answer score: 3