$\mbox{Prove } 1 + 2 + \dots + n = \frac{(1+n)n}{2} \quad n \geq 0 $
\[ \mbox{when } n = 1\,, \quad 1 = \frac{(1+1)1}{2} = 1 \\ \mbox{when } n = 2\,, \quad 1 + 2 = \frac{(1 + 2)2}{2} = 3 \\ \mbox{Assume the formula is true for } n = k > 2 \\ \Rightarrow 1 + 2 + \dots + k = \frac{(1+k)k}{2} \\ \] $\mbox{Inductive step}$ \begin{align} \mbox{LS } &= 1 + 2 + \dots + k + (k + 1) \\ \mbox{RS } &= \frac{(1 + k)k}{2} + (k+1) \\ \mbox{RS } &= \frac{(1 + k)k}{2} + \frac{2(k+1)}{2} \\ \mbox{RS } &= \frac{(2+k)(k+1)}{2}\\ \mbox{RS } &= \frac{(1+(k+1))(k+1)}{2}\\ \Rightarrow \mbox{LS} &= \mbox{RS for } n = k + 1 \\ \Rightarrow 1 + 2 + \dots + n &= \frac{(1+n)n}{2} \mbox{ for all } n \geq 0 \\ \end{align}