Ниже — несколько разных доказательств тождества и краткое обсуждение обобщаемости на несмежные последовательности.
1) Индукция.
База: для $n=1$ верно: $1=\frac{1\cdot 2}{2}$.
Переход: предположим $\sum _{k=1}^{n}k=\frac{n(n+1)}{2}$. Тогда
$$\sum _{k=1}^{n+1}k=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}.$$ Значит формула верна для всех $n$.
2) Парное суммирование (метод Гаусса).
Сложим ряд в прямом и обратном порядке:
$$(1+2+\cdots +n)+(n+\cdots +2+1)=n(n+1).$$ Слева две одинаковые суммы, значит
$$2\sum _{k=1}^{n}k=n(n+1),\sum _{k=1}^{n}k=\frac{n(n+1)}{2}.$$
3) Комбинаторный (счет пар).
Число двуэлементных подмножеств множества $\{1,\dots ,n+1\}$ равно $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$. Считая эти пары по максимальному элементу: если максимум равен $k+1$, есть ровно $k$ пар, $k=1,\dots ,n$. Поэтому
$$\sum _{k=1}^{n}k=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=\frac{n(n+1)}{2}.$$
4) Телескопирование через биномиальные коэффициенты.
Заметим
$$k=\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)-\left(\genfrac{}{}{0ex}{}{k}{2}\right).$$ Просуммировав по $k=1$ до $n$, получаем телескопию и
$$\sum _{k=1}^{n}k=\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)=\frac{n(n+1)}{2}.$$
5) Аппроксимация многочленом / метод конечных разностей.
Если $S(n)={\sum }_{k=1}^{n}k$, то $S(n)$ — многочлен степени 2. Подставив $n=0,1,2$ или используя конечные разности, находим
$$S(n)=\frac{n^2+n}{2}.$$
Краткое обсуждение обобщаемости на несмежные последовательности.
- Парное суммирование обобщается на любые арифметические прогрессии: для $n$ членов с первым $a_1$ и последним $a_n$ справедливо $\sum _{k=1}^n{a}_k=\frac{n(a_1+a_n)}{2}$, потому что пары симметричны. Для произвольной (несимметричной) несмежной последовательности этот метод, в общем, неприменим.
- Комбинаторное и телескопическое доказательства используют структурную интерпретацию членов (число пар, разность биномиальных коэффициентов). Эти методы обобщаются на последовательности, которые имеют комбинаторный смысл или которые можно представить как разности более простых последовательностей (например, если $a_k=\left(\genfrac{}{}{0ex}{}{k+r}{r}\right)$ или вообще полиномиальные по $k$ величины).
- Метод конечных разностей / многочленов обобщается широко: если члены последовательности $a_k$ выражаются полиномом степени $d$ по $k$, то сумма ${\sum }_{k=1}^n{a}_k$ — полином степени $d+1$, и его можно найти тем же приёмом (интерполяция, разности). Это даёт точные формулы для многих несмежных (например, полиномиальных) последовательностей.
- Индукция — это способ доказательства любой предполагаемой формулы, но сама по себе не даёт замысл формулы; она применима ко всем последовательностям, для которых вы угадаете (или выведете) замкнутую форму.
Итого: парный метод наиболее прост для арифметических прогрессий; телескопирование и метод конечных разностей (или представление через биномиальные коэффициенты) — самые универсальные для обобщения на множества последовательностей, члены которых выражаются полиномами или разностями более простых функций.