Closed form for the recurrence T(n) = T(n-1) + n²
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) &amp;\leq (n + 1)^3 c_3 + (n + 1)^2 c_2 + (n + 1) c_1 + c_0 \\
T(n) + (n + 1)^2 &amp;\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 &amp;= 1/3 \\
c_2 &amp;= 1/2 \\
c_1 &amp;= 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
$$