Proving a recurrence relation via induction

Question

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?

Answer 1

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$.