Solve T(1) = 1 T(n) = T(n-1) + n^2 for n ≥ 2

I am not able to solve the following recurrence relation:

$$T(n) = \begin{cases} T(n-1) + n^2 & \text{if } n \ge 2, \\ 1 & \text{otherwise.}\\ \end{cases}$$

How do I start?

• Search up the master's theorem in google. – nir shahar Mar 10 at 20:28
• Sum all the instances of the recurrence for $n=2,3,...,m$ and cancel the terms that appear on both sides. You get $T(m)=T(1)+2^2+3^2+...+m^2=1+2^2+3^2+...+m^2=\frac{m(m+1)(2m+1)}{6}$. – plop Mar 10 at 21:47
• @nir shahar, that’s quite useless advice. Master’s theorem can’t be used here. – gnasher729 Mar 11 at 19:26
• Does this answer your question? Solving or approximating recurrence relations for sequences of numbers – xskxzr Mar 18 at 11:41

$$T(n)=T(1)+\sum_{i=2}^{n}i^2$$ $$T(n)=T(1)+\sum_{i=1}^{n}i^2-\sum_{i=1}^{1}i^2$$
So as @plop mentioned in comments, we have: $$\lim_{n\to \infty} T(n)=\frac{n(n+1)(2n+1)}{6}=O(n^3)$$