Утверждение: для любого натурального $n$ $$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}.$$
1) Индукция.
- База: при $n=1$ левая часть $1$, правая $\frac{1\cdot 2}{2}=1$.
- Шаг: предположим верно для $n$, т.е.
$$\sum _{k=1}^{n}k=\frac{n(n+1)}{2}.$$ Тогда
$$\sum _{k=1}^{n+1}k=\sum _{k=1}^{n}k+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2},$$ что равнозначно формуле при $n+1$. По принципу математической индукции утверждение верно для всех натуральных $n$.
2) Парное сложение (метод Гаусса).
Пусть $S={\sum }_{k=1}^{n}k$. Тогда записав сумму в прямом и обратном порядке и сложив по членам,
$$S=1+2+\cdots +n,S=n+(n-1)+\cdots +1,$$ $$2S=\sum _{k=1}^n(k+(n+1-k))=\sum _{k=1}^n(n+1)=n(n+1).$$ Отсюда $S=\frac{n(n+1)}{2}$.
3) Комбинаторное доказательство.
Рассмотрим число двузначных (двухэлементных) подмножеств множества $\{1,2,\dots ,n+1\}$. Оно равно $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=\frac{(n+1)n}{2}$. С другой стороны, если считать по наибольшему элементу множества: для наибольшего элемента $j$ (где $j=2,\dots ,n+1$) есть ровно $j-1$ пар, значит общее число пар
$$\sum _{j=2}^{n+1}(j-1)=\sum _{k=1}^{n}k.$$ Следовательно ${\sum }_{k=1}^{n}k=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=\frac{n(n+1)}{2}$.
(Все три подхода дают одну и ту же формулу.)