# How to solve T(n) = T(n-1) + n^2?

See title. I'm trying to apply the method from this question. What I have so far is this, but I don't know how to proceed from here on:

T(n) = T(n-1) + n2

T(n-1) = T(n-2) + (n-1)2 = T(n-2) + n2 - 2n + 1

T(n-2) = T(n-3) + (n-2)2 = T(n-3) + n2 - 4n + 4

T(n-3) = T(n-4) + (n-3)2 = T(n-4) + n2 - 6n + 9

Substituting the values of T(n-1), T(n-2) and T(n-3) into T(n) gives:

T(n) = T(n-2) + 2n2 - 2n + 1

T(n) = T(n-3) + 3n2 - 6n + 5

T(n) = T(n-4) + 4n2 - 12n + 14

Now I have to find a pattern but I don't really know how to do that. What I got is:

T(n) = T(n-k) + kn2 - ...???

• possible duplicate of Solving or approximating recurrence relations for sequences of numbers
– D.W.
Jun 10 '15 at 2:07
• @D.W. Since the OP did actually try and do something (and Rick's answer is outstanding), I think we can keep this one.
– Raphael
Jun 10 '15 at 7:40
• Suggested to use Tex formatting for mathematical formulae.
– hola
Nov 23 '19 at 10:57

Don't expand the squared terms; it'll just add confusion. Think of the recurrence as $$T(\fbox{foo}) = T(\fbox{foo}-1)+\fbox{foo}\;^2$$ where you can replace foo with anything you like. Then from $$T(n)=T(n-1)+n^2$$ you can replace $T(n-1)$ by $T(n-2)+(n-1)^2$ by putting $n-1$ in the boxes above, yielding $$T(n) = [T(n-2) + (n-1)^2]+n^2 = T(n-2)+(n-1)^2+n^2$$ and similarly \begin{align} T(n) &= T(n-2)+(n-1)^2+n^2\\ &= T(n-3)+(n-2)^2+(n-1)^2+n^2\\ &= T(n-4)+(n-3)^2+(n-2)^2+(n-1)^2+n^2 \end{align} and in general you'll have $$T(n) = T(n-k)+(n-k+1)^2+(n-k+2)^2+\dotsm+(n-1)^2+n^2$$ Now if we let $k=n$ we'll have $$T(n) = T(0)+1^2+2^2+3^2+\dotsm+n^2$$ Now if you just need an upper bound for $T(n)$ observe that $$1^2+2^2+3^2+\dotsm+n^2\le \underbrace{n^2+n^2+n^2+\dotsm+n^2}_n=n^3$$ so we conclude that $T(n)=O(n^3)$, in asymptotic notation.

For a more exact estimate, you can look up the equation for the sum of squares: $$1^2+2^2+\dotsm+n^2=\frac{n(n+1)(2n+1)}{6}$$ so $$T(n)=T(0)+\frac{n(n+1)(2n+1)}{6}$$

• Really clear explanation, thanks a lot!
– Ken
Jun 9 '15 at 22:48

\begin{align} T(k) - T(k - 1) &= k^2 \\ \sum_{1 \le k \le n} (T(k) - T(k - 1)) &= \sum_{1 \le k \le n} k^2 \\ T(n) - T(0) &= \frac{n (n + 1) (2 n + 1)}{6} \end{align}