need the steps on how to do this recurrence relation question

Question

Given $T_0=0 $ and $T_n=T_{n−1}+n \forall n\in \mathbb N$ use the method of substitution to derive an explicit formula for $T_n$. Prove the validity if your formula.

Answer 1

If $T_n = T_{n-1} + n$, then $T_{n-1} = T_{n-2} + (n-1)$, so actually $\color{}{T_n = T_{n-2} + n+(n-1).}$

But I lied, $T_{n-2} = T_{n-3} + (n-2)$. So actually, $\color{}{T_n = T_{n-3} + n + (n-1) + (n-2).}$

Continuing this till $T_{n-n} = T_0$, we have,

$$T_n = T_0 + \sum_{k=0}^n(n-k)= \frac{n(n+1)}{2}.$$

---

Now we have to prove that this result is valid. We do this by induction on $n$.

For $n=0$, we have $T_0 = 0$. Assume for some fixed $n$, that $T_n= \frac{n(n+1)}{2}$. From the recurrence, we know that $T_{n+1} = T_{n} + (n+1)$. But by the inductive hypothesis, we have $$T_{n+1} = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}.$$ So, by mathematical induction, our formula satisfies the recurrence relation $T_n = T_{n-1} + n$.