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)& = T(n-2) + c(n-1)^2\\T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex]T(n-2) &= T(n-3) + c(n-2)^2\\T(n) & = T(n-3) + c(n-2)^2 + c(n-1)^2 + cn^2 \\[1ex]T(n-3) &= T(n-4) + c(n-3)^2 \\T(n) &= 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.
Recurrence relation for time complexity $T(n) = T(n-1) + n^2$
time complexity;algorithm analysis;proof techniques;recurrence relation
Just continue your reasoning as follows.\begin{eqnarray}T(n) &=& T(n-1) + cn^2 \\&=& T(n-2) + c(n-1)^2 + cn^2 \\&=& \ldots \\&=& T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\&=& 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?   