# 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?

We can prove easily in induction, that $$T(n)=c + \sum_{i=1}^n i$$. Assume correctness for $$n$$, we will prove for $$n+1$$. Clearly, $$T(n+1)=T(n)+(n+1)=c + n+1 + \sum_{i=1}^n i = c + \sum_{i=1}^{n+1} i$$.
A nice result you are probably familiar with, if you learned about arithmetic progression series, is that $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$
Thus, $$T(n) = c + \frac{n(n+1)}{2} = \Theta(n^2)$$
$$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)$$