Closed Form for Triangular Numbers/Proof using Binomial Coefficients

Theorem

The closed-form expression for the $n$th triangular number is:

$\ds T_n = \sum_{i \mathop = 1}^n i = \frac {n \paren {n + 1} } 2$

Proof

From Binomial Coefficient with One:

$\forall k \in \Z, k > 0: \dbinom k 1 = k$

Thus:

\(\ds \sum_{k \mathop = 1}^n k\)

\(=\)

\(\ds \sum_{k \mathop = 1}^n \binom k 1\)

Binomial Coefficient with One

\(\ds \)

\(=\)

\(\ds \binom {n + 1} 2\)

Sum of k Choose m up to n‎

\(\ds \)

\(=\)

\(\ds \frac {\paren {n + 1} n} 2\)

Definition of Binomial Coefficient

$\blacksquare$

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients