I have to prove that the bound of the following relation is $\theta(n^2)$ by induction-
$$T(n) = T(n-1) + n$$
- should i seprate my induction into two sections - to claim that $T(n) = O(n^2)$ and $T(n) = \Omega(n^2)$ and prove each case, or should i expand the relation and then formulate my claims ?
- should my two equations be the same , but with diffrent sign --> $\leq$ and $\geq$
Thanks!
Another path to spread a different light. From the identity, $$ T_{n} = T_{n-1} + n, \qquad n=1,2,3,\ldots, $$ one may obtain $$ T_{n} - T_{n-1} = n, $$ then summing from $n=1$ to $n=N$ terms telescope, $$ T_N- T_0=\sum_{n=1}^{N}n, $$ that is $$ T_N- T_0=\frac{N(N+1)}2 $$ giving, as $N \to \infty$,
as wanted.