$T(n)=T(n-1)+n$, $T(1)=1$ — Solve by Iteration / Substitution

Iterative Unfolding:
$$\begin{aligned} T(n) &= T(n-1)+n \\ &= [T(n-2)+(n-1)]+n = T(n-2)+(n-1)+n \\ &= [T(n-3)+(n-2)]+(n-1)+n \\ &\;\vdots \\ &= T(1) + 2+3+\dots+n \\ &= 1 + \sum_{k=2}^{n} k = \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \end{aligned}$$

Substitution Proof: Guess $T(n)=n(n+1)/2$.

• Base $n=1$: $1\cdot2/2=1$ ✓
• Step: assume $T(n-1)=(n-1)n/2$ → $T(n)=(n-1)n/2 + n = n(n+1)/2$ ✓

Asymptotics:
$$T(n)=\frac{n^2}{2}+\frac{n}{2}=\Theta(n^2) = O(n^2), \Omega(n^2)$$

Application: Sum of first $n$ naturals; time of naive incremental algorithms (e.g., insertion sort worst-case without divide).