# 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:

1. $c_1 = c_1 + 3$
2. $c_2 = c_2 - 2c_1 - 1$
3. $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*}

$$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:

1. $c_3 = c_3$
2. $c_2 = 3c_3 + c_2 - 1$
3. $c_1 = 3c_3 + 2c_2 + c_1 - 2$
4. $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

• I'm not sure why you are expanding $T(n+1)$ though. – Shoe Jul 11 '15 at 1:04
• @Jefffrey why not? Personal preference for $-$ over $+$, I suppose. – muru Jul 11 '15 at 1:07
• @Jefffrey Ok, I'll bite. What would you do instead, and how would it be better? – muru Jul 11 '15 at 1:25
• You have a typo: $T(n) = O(n^3)$ rather than $T(n) = O(n)$. – Yuval Filmus Jul 11 '15 at 3:23
• @Jefffrey sure, it has $T(n-1)$ in the recursive step. What of it? I can replace $n$ with $y+1$ and get an equivalent recursion, and expanding $(y+1)^3$ frees me from juggling the signs involved in $(n-1)^3$. – muru Jul 11 '15 at 11:08

Hint: Expanding the recurrence, we get that $$T(n) = n^2 + (n-1)^2 + \cdots + 1^2 + T(0).$$ It is known that $$\sum_{m=1}^n m^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3).$$

• Does that mean that it's not possible to use the substitution method here? – Shoe Jul 10 '15 at 20:24
• Since there is an exact formula, you can definitely use the substitution method. You must have made a mistake in your calculation above. – Yuval Filmus Jul 10 '15 at 20:33