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&gt;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).
$$