recurrence relation with induction

Question

The following recurrence relation: $T(n)=T(n-1)+n=1+\frac{n^2+n}{2}=\theta(n^2)$, so this mean that: there is $c_1, c_2, n_o > 0 : c_1n^2<=1+\frac{n^2+n}{2}<=c_2n^2$, the second inequality it's easy, but how to prove by induction the first: $c_1n^2<=1+\frac{n^2+n}{2}$?

Answer 1

Choose $c_1=1/2$, then you can directly see that

$$c_1n^2\le 1+\frac{n^2+n}{2}$$

If you want to use induction, you get with $c_1=1/2$

$$\frac{(n+1)^2}{2}\le 1+\frac{(n+1)^2}{2}+\frac{(n+1)}{2}$$

This is equivalent to

$$0\le 1+\frac{(n+1)}{2}$$ which is obviously satisfied for all $n\ge 0$.

Answer 2

You can solve this exactly: $$ \begin{align*} T(n) - T(n - 1) &= \frac{n^2 - n + 2}{2} \\ \sum_{1 \le n \le m} (T(n) - T(n - 1)) &= \frac{1}{2} \left( \sum_{1 \le n \le m} n^2 - \sum_{1 \le n \le m} n + 2 m \right) \\ T(m) &= T(0) + \frac{m^3 - m + 6}{6} \end{align*} $$