Recurrence relation for time complexity $T(n) = T(n-1) + n^2$ I'm looking for a $\Theta$ approximation of
$$T(n) = T(n-1) + cn^{2}$$

This is what I have so far:

$$
\begin{align*}
T(n-1)&amp; = T(n-2) + c(n-1)^2\\
T(n) &amp;= T(n-2) + c(n-1) + cn^2\\[1ex]
T(n-2) &amp;= T(n-3) + c(n-2)^2\\
T(n) &amp; = T(n-3) + c(n-2)^2 + c(n-1)^2 + cn^2 \\[1ex]
T(n-3) &amp;= T(n-4) + c(n-3)^2 \\
T(n) &amp;= T(n-4) + c(n-3)^2 + c(n-2)^2 + c(n-1)^2 + cn^2
\end{align*}
$$

So, at this point I was going to generalize and substitute $k$ into the equation.

$$T(n)= T(n-k) + (n-(k-1))^2 + c(k-1)^2$$

Now, I start to bring the base case of 1 into the picture. On a couple of previous, more simple problems, I was able to set my generalized k equation equal to 1 and then solve for $k$. Then put $k$ back into the equation to get my ultimate answer.

But I am totally stuck on the $(n-k+1)^2$ part. I mean, should I actually foil all this out? I did it and got $k^2-2kn-2k+n^2 +2n +1 = 1$. At this point I'm thinking I totally must have done something wrong since I've never see this in previous problems.

Could anyone offer me some help with how to solve this one? I would greatly appreciate it. I also tried another approach where I tried to set $n-k = 0$ from the last part of the equation and got that $k = n$. I plugged n back into the equation towards the end and ultimately got $n^2$ as an answer. I have no clue if this is right or not.

I am in an algorithms analysis class and we started doing recurrence relations and I'm not 100% sure if I am doing this problem correct. I get to a point where I am just stuck and don't know what to do. Maybe I'm doing this wrong, who knows. The question doesn't care about upper or lower bounds, it just wants a theta.
Just continue your reasoning as follows.

\begin{eqnarray}
T(n) &amp;=&amp; T(n-1) + cn^2 \\
&amp;=&amp; T(n-2) + c(n-1)^2 + cn^2 \\
&amp;=&amp; \ldots \\
&amp;=&amp; T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\
&amp;=&amp; T(0) +c\sum_{1\leq i\leq n} i^2.
\end{eqnarray}   

Do you know how to simplify this using the addition formula for the first $n$ squares?