# Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$

I try to prove that the asymptotics of the recurrence $$T(n) = T(n-1) + \Theta (n)$$ is $$T(n) = \Theta(n^2)$$.

By $$\Theta$$, I mean tight bound from above and below.

I can write the equation like this: $$T(n) = T(n-1) + \Theta (n) = T(n-1) + cn.$$

I'm having a hard time proving the lower bound with this method, do you have any idea how?

What I did for Upper bound is:

Assume: $$T(n-1) \leq c(n-1)^2, \quad c \in R$$

Therefore: $$T(n) \leq c(n-1)^2 + cn = cn^2 - 2cn + c + cn = cn^2 - cn + c \leq cn^2$$

Therefore I get: $$T(n) \leq O(n^2)$$

For $$O$$, by which I mean just an upper bound.

So, how do I prove a matching lower bound using this method?

Let $$f(n) = \Theta(n)$$. Thus there are $$N,a,b>0$$ such that for $$n \geq N$$, we have $$an \leq f(n) \leq bn$$.
Now suppose that $$T(n) = T(n-1) + f(n)$$, with some base case $$T(0) = C$$. Unrolling the sum, $$T(n) = C + f(1) + \cdots + f(n).$$ Let $$D = C + f(1) + \cdots + f(N-1)$$. For $$n \geq N$$, $$T(n) \leq D + b(N + \cdots + n) = D + b\frac{(n-N+1)(n+N)}{2} = O(n^2).$$ Similarly, $$T(n) \geq D + a(N + \cdots + n) = D + a\frac{(n-N+1)(n+N)}{2} = \Omega(n^2).$$