Sum of the first n naturals

Example — Sum of the first $n$ naturals

We prove that, for every $n\ge 1$, $P(n)\colon\quad 1+2+\cdots+n = \frac{n(n+1)}{2}.$ Base ($n=1$): $1=\dfrac{1\cdot 2}{2}$. True.

Step: suppose $P(k)$ is true, that is $1+\cdots+k=\dfrac{k(k+1)}{2}$. Then $1+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = (k+1)\frac{k+2}{2} = \frac{(k+1)(k+2)}{2},$ which is exactly $P(k+1)$. By induction, the formula holds for every $n\ge 1$. ∎

Links

Topics: Set theory
Concepts: Principle of induction
Methods: Induction
Skills: Proving