# Proving a recurrence relation via induction

I need to prove that $$T(n)$$ is $$O(n^2)$$ using only the definition of $$O$$ and induction.
I don't want a solution that "finds" a pattern in $$T(n)$$.
Here, $$T(1)=1$$ and $$T(n) = T(n-1) + n$$.
By the definition of $$O$$, we have to prove that: $$\exists c > 0, n_0 > 0, \ \ T(n) \le cn^2 \ \forall \ n \ge n_0$$
Let $$n_0 = 1.$$
I shall try to accomplish this via induction on $$n$$:
Basis step: $$n = 1$$
$$T(1) = 1 \le c^2 \ \ \forall c \gt 1$$
Inductive Step:
Inductive Hyposthesis: $$T(n) \le cn^2 \ \forall \ n \ge 1$$ for $$n = k-1, k-1 \ge 1$$.
To prove: $$T(n) \le cn^2 \ \forall \ n \ge 1$$ for $$n = k$$
$$T(k) = T(k-1) + k$$ $$T(k) \le c(k-1)^2 + k \hspace{1em} \text{(by the inductive hyposthesis) }$$ $$T(k) \le ck^2 + (1- 2c)k + c$$ How shall I proceed further with the proof?

• @Peter I know that would be a much simpler and elegant way of proving the claim, but I specifically want to use the the definition of $O$ (in terms of $c, n_0$) to prove this. Sep 14, 2020 at 13:03
• @Peter Sorry, there was an error on my part while typing the question. Have fixed it now, it is $T(n-1) + n$ Sep 14, 2020 at 13:13
• $O(n^2)$ does not mean that the function is bounded from above by $n$ times a constant. And in fact, $T(n)$ grows faster than any linear function $an+b$. Sep 14, 2020 at 13:29

Edit: so it is $$T(n) = T(n-1) + n = n(n+1)/2$$ which is obviously $$O(n^2)$$. If you want to check it explicitly without using that, you can choose $$c=2$$ and the induction step would be \begin{align*} T(n) \leq c(n-1)^2 + n = 2n^2 - 3n +2 \leq 2n^2 \end{align*} since $$n\geq 1$$.