Solving recurrence $T(n) = T(n - 1) + n$ with substitution method How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method?
I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$:
$$T(n) \leq O(n^2) \\  \leq c(n-1)^2+n \\ \leq cn^2+c-2cn+n$$
How can i continue?
$$T(n)=T(n-1)+n=\\=T(n-2)+(n-1)+n=\\=\cdots=\\
=T(1)+2+\cdots+(n-1)+n =\\= T(1) + \frac{n(n+1)}{2}-1 \in \Theta(n^2)$$