Closed Form for Triangular Numbers

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$

Plainly stated: the sum of the first $n$ natural numbers is equal to $\dfrac {n \paren {n + 1} } 2$.

This formula pops up frequently in fields as differing as calculus and computer science, and it is elegant in its simplicity.

Direct Proof

We have that:

$\ds \sum_{i \mathop = 1}^n i = 1 + 2 + \cdots + n$

Consider $\ds 2 \sum_{i \mathop = 1}^n i$.

Then:

 $\ds 2 \sum_{i \mathop = 1}^n i$ $=$ $\ds 2 \paren {1 + 2 + \dotsb + \paren {n - 1} + n}$ $\ds$ $=$ $\ds \paren {1 + 2 + \dotsb + \paren {n - 1} + n} + \paren {n + \paren {n - 1} + \dotsb + 2 + 1}$ $\ds$ $=$ $\ds \paren {1 + n} + \paren {2 + \paren {n - 1} } + \dotsb + \paren {\paren {n - 1} + 2} + \paren {n + 1}$ Integer Addition is Commutative, Integer Addition is Associative $\ds$ $=$ $\ds \paren {n + 1}_1 + \paren {n + 1}_2 + \dotsb + \paren {n + 1}_n$ $\ds$ $=$ $\ds n \paren {n + 1}$

So:

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

$\blacksquare$

Proof by Telescoping Sum

Observe that:

 $\ds \sum_{i \mathop = 1}^n \paren {\paren {i + 1}^2 - i^2}$ $=$ $\ds -\sum_{i \mathop = 1}^n \paren {i^2 - \paren {i + 1} ^2}$ $\ds$ $=$ $\ds -\paren {1 - \paren {n + 1}^2}$ Telescoping Series $\ds$ $=$ $\ds \paren {n + 1}^2 - 1$

Moreover, we have:

$\paren {i + 1}^2 - i^2 = 2 i + 1$

And also:

$\paren {n + 1}^2 - 1 = n^2 + 2 n$

Combining these results, we obtain:

 $\ds n + 2 \sum_{i \mathop = 1}^n i$ $=$ $\ds n^2 + 2 n$ $\ds \leadsto \ \$ $\ds 2 \sum_{i \mathop = 1}^n i$ $=$ $\ds n \left({n + 1}\right)$ $\ds \leadsto \ \$ $\ds \sum_{i \mathop = 1}^n i$ $=$ $\ds \frac {n \paren {n + 1} } 2$

This concludes the proof.

$\blacksquare$

Proof by Recursion

We have that:

$\ds \map T n = 1 + 2 + \dotsb + n = \sum_{i \mathop = 1}^n i$

Thus:

 $\ds \map T n$ $=$ $\ds n + \paren {n - 1} + \paren {n - 2} + \dotsb + 2 + 1$ $\ds$ $=$ $\ds n + \paren {n - 1} + \paren {n - 2} + \dotsb + \paren {n - \paren {n - 2} } + \paren {n - \paren {n - 1} }$ $\ds$ $=$ $\ds \underbrace {n + n + \dotsb + n}_{n \text { times} }$ extracting $n$ from each term $\ds$  $\, \ds + \,$ $\ds \paren {-1} + \paren {-2} + \dotsb + \paren {-\paren {n - 2} } + \paren {-\paren {n - 1} }$ $\ds$ $=$ $\ds n^2 - \paren {1 + 2 + \dotsb + \paren {n - 1} }$ $\text {(1)}: \quad$ $\ds \leadsto \ \$ $\ds \map T n$ $=$ $\ds n^2 - \map T {n - 1}$

Then:

 $\text {(2)}: \quad$ $\ds \map T n$ $=$ $\ds n + \map T {n - 1}$ Definition 1 of Triangular Number $\ds \leadsto \ \$ $\ds 2 \, \map T n$ $=$ $\ds n^2 + n$ $(1) + (2)$ $\ds \leadsto \ \$ $\ds \map T n$ $=$ $\ds \frac {n \paren {n + 1} } 2$

$\blacksquare$

Proof by Induction

Proof by induction:

Basis for the Induction

When $n = 1$, we have:

$\ds \sum_{i \mathop = 1}^1 i = 1$

Also:

$\dfrac {n \paren {n + 1} } 2 = \dfrac {1 \cdot 2} 2 = 1$

This is our base case.

Induction Hypothesis

$\forall k \in \N: k \ge 1: \ds \sum_{i \mathop = 1}^k i = \frac {k \paren {k + 1} } 2$

This is our induction hypothesis.

It is to be demonstrated that:

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

Induction Step

This is our induction step:

Consider $n = k + 1$.

By the properties of summation:

$\ds \sum_{i \mathop = 1}^{k + 1} i = \sum_{i \mathop = 1}^k i + k + 1$

Using the induction hypothesis this can be simplified to:

 $\ds \frac {k \paren {k + 1} } 2 + k + 1$ $=$ $\ds \frac {k \paren {k + 1} + 2 k + 2} 2$ $\ds$ $=$ $\ds \frac {k^2 + 3 k + 2} 2$ $\ds$ $=$ $\ds \frac {\paren {k + 1} \paren {k + 2} } 2$ $\ds$ $=$ $\ds \frac {\paren {k + 1} \paren {\paren {k + 1} + 1} } 2$

Hence the result by induction.

$\blacksquare$

Proof by Arithmetic Sequence

 $\ds \sum_{i \mathop = 0}^{m - 1} \paren {a + i d}$ $=$ $\ds m \paren {a + \frac {m - 1} 2 d}$ Sum of Arithmetic Sequence $\ds \sum_{i \mathop = 0}^n \paren {a + i d}$ $=$ $\ds \paren {n + 1} \paren {a + \frac n 2 d}$ Let $n = m - 1$ $\ds \sum_{i \mathop = 0}^n i$ $=$ $\ds \paren {n + 1} \paren {\frac n 2}$ Let $a = 0$ and $d = 1$ $\ds 0 + \sum_{i \mathop = 1}^n i$ $=$ $\ds \frac {n \paren {n + 1} } 2$ $\ds \sum_{i \mathop = 1}^n i$ $=$ $\ds \frac {n \paren {n + 1} } 2$

$\blacksquare$

Proof by Polygonal Numbers

Triangular numbers are $k$-gonal numbers where $k = 3$.

From Closed Form for Polygonal Numbers we have that:

$P \left({k, n}\right) = \dfrac n 2 \left({\left({k - 2}\right) n - k + 4}\right)$

Hence:

 $\ds T_n$ $=$ $\ds \frac n 2 \left({\left({3 - 2}\right) n - 3 + 4}\right)$ Closed Form for Polygonal Numbers $\ds$ $=$ $\ds \frac n 2 \left({n + 1}\right)$

Hence the result.

$\blacksquare$

Proof using Binomial Coefficients

$\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 {\left({n+1}\right) n} 2$ Definition of Binomial Coefficient

$\blacksquare$

Proof using Cardinality of Set

Let $\N_n^* = \set {1, 2, 3, \cdots, n}$ be the initial segment of natural numbers.

Let $A = \set {\tuple {a, b}: a \le b, a, b \in \N_n^*}$

Let $B = \set {\tuple {a, b}: a \ge b, a, b, \in \N_n^*}$

Let $\phi: A \to B$ be the mapping:

$\map \phi {x, y} = \tuple {y, x}$

By definition of dual ordering, $\phi$ is a bijection:

$(1): \quad \size A = \size B$

We have:

 $\ds A \cup B$ $=$ $\ds \set {\tuple {a, b}: a, b \in \N_n^*}$ $\ds A \cap B$ $=$ $\ds \set {\tuple {a, b}: a = b: a, b \in \N_n^*}$

Thus:

 $\ds \size A + \size B$ $=$ $\ds \size {A \cup B} + \size {A \cap B}$ Inclusion-Exclusion Principle $\ds$ $=$ $\ds n^2 + n$ Count of a finite set

Combined with $\left({1}\right)$ this yields:

$\size A = \dfrac {n^2 + n} 2 = \dfrac {n \paren {n + 1} } 2$

It remains to prove that:

$T_n = \size A$
 $\ds T_n$ $=$ $\ds \sum_{i \mathop = 1}^n i$ Definition of $T_n$ $\ds$ $=$ $\ds \sum_{i \mathop \in \N_n^*} i$ $\ds$ $=$ $\ds \sum_{i \mathop \in \N_n^*} \size {\set {a: a \in \N_i^*} }$ Count of Finite Set,Definition of Initial Segment of One-Based Natural Numbers $\ds$ $=$ $\ds \size {\set {\tuple {a, i} :a\in \N_i^*, i \in \N_n^*} }$ Inclusion-Exclusion Principle, sets are mutually exclusive as their second argument in the ordered pair are different $\ds$ $=$ $\ds \size {\set {\tuple {a, b}: a \le b, a, b \in \N_n^*} }$ Change of Variable, Definition of Initial Segment of One-Based Natural Numbers $\ds$ $=$ $\ds \size A$ Definition of $A$

$\blacksquare$

Proof using Odd Number Theorem

 $\ds \sum_{j \mathop = 1}^n \paren {2 j - 1}$ $=$ $\ds n^2$ Odd Number Theorem $\ds \leadsto \ \$ $\ds \sum_{j \mathop = 1}^n \paren {2 j - 1} + \sum_{j \mathop = 1}^n 1$ $=$ $\ds n^2 + n$ $\ds \leadsto \ \$ $\ds \sum_{j \mathop = 1}^n \paren {2 j}$ $=$ $\ds n \paren {n + 1}$ $\ds \leadsto \ \$ $\ds \sum_{j \mathop = 1}^n j$ $=$ $\ds \frac {n \paren {n + 1} } 2$

$\blacksquare$

Proof using Bernoulli Numbers

 $\ds \sum_{i \mathop = 1}^n i^p$ $=$ $\ds 1^p + 2^p + \cdots + n^p$ $\ds$ $=$ $\ds \frac {n^{p + 1} } {p + 1} + \sum_{k \mathop = 1}^p \frac {B_k \, p^{\underline {k - 1} } \, n^{p - k + 1} } {k!}$

where $B_k$ are the Bernoulli numbers.

Setting $p = 1$:

 $\ds \sum_{i \mathop = 1}^n i^1$ $=$ $\ds 1 + 2 + \cdots + n$ $\ds$ $=$ $\ds \frac {n^2} 2 + \frac {B_1 \, p^{\underline 0} n^1} {1!}$ $\ds$ $=$ $\ds \frac {n^2} 2 + \frac 1 2 \frac {1 \times n} 1$ Definition of Bernoulli Numbers, Number to Power of Zero Falling is One $\ds$ $=$ $\ds \frac {n^2 + n} 2$

Hence the result.

$\blacksquare$

Also see

$\ds \int_0^b x \rd x = \frac {b^2} 2$

Historical Note

Some sources report that the closed-form expression for the $n$th triangular number was proved by Archimedes during the course of his proofs of the volumes of various solids of revolution in his On Conoids and Spheroids.

Others suggest that it was known as far back as Pythagoras of Samos, circa $550$ B.C.E.