Closed Form for Triangular Numbers

Theorem

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

$\displaystyle T_n = \sum_{i=1}^{n} i = \frac {n \left({n+1}\right)} {2}$

Plainly stated: the sum of the first $n$ natural numbers is equal to $\displaystyle \frac {n \left({n+1}\right)} 2$.

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

Proofs

Direct Proof

We have that $\displaystyle \sum_{i=1}^n i = 1 + 2 + \cdots + n$.

Consider $\displaystyle 2 \sum_{i=1}^n i$. Then:

	\(\displaystyle \)	\(\displaystyle 2 \sum_{i=1}^n i\)	\(=\)	\(\displaystyle 2 \left({1 + 2 + \cdots + n}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({1 + 2 + \cdots + n}\right) + \left({1 + 2 + \cdots + n}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({1 + n}\right) + \left({2 + \left({n-1}\right)}\right) + \cdots + \left({\left({n-1}\right) + 2}\right) + \left({n + 1}\right)\)	\(\displaystyle \)	by commutativity and associativity
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({n + 1}\right)_1 + \left({n + 1}\right)_2 + \cdots + \left({n + 1}\right)_n\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle n \left({n + 1}\right)\)	\(\displaystyle \)

So:

	\(\displaystyle \)	\(\displaystyle 2 \sum_{i=1}^n i\)	\(=\)	\(\displaystyle n \left({n + 1}\right)\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \sum_{i=1}^n i\)	\(=\)	\(\displaystyle \frac {n \left({n+1}\right)} 2\)	\(\displaystyle \)

$\blacksquare$

This is the method employed by Gauss who, when very young (according to the apocryphal story), calculated the sum of the numbers from $1$ to $100$ before the teacher had barely sat back down after setting the assignment.

Direct Proof by using Telescoping Sum

Observe that:

	\(\displaystyle \)	\(\displaystyle \sum_{i=1}^n \left({ \left({i+1}\right)^2 - i^2 }\right)\)	\(=\)	\(\displaystyle -\sum_{i=1}^n \left({ i^2 - \left({i+1}\right)^2 }\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle - \left({1 - \left({n+1}\right)^2}\right)\)	\(\displaystyle \)	since this is a telescoping sum
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({n+1}\right)^2 - 1\)	\(\displaystyle \)

Moreover, we have:

$ \left({i + 1}\right)^2 - i^2 = 2 i + 1$

And also:

$ \left({n + 1}\right)^2 - 1 = n^2 + 2 n$

Combining these results, we obtain:

	\(\displaystyle \)	\(\displaystyle n + 2 \sum_{i=1}^n \, i\)	\(=\)	\(\displaystyle n^2 + 2 n\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle 2 \sum_{i=1}^n \, i\)	\(=\)	\(\displaystyle n \left({n + 1}\right)\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle \sum_{i=1}^n \, i\)	\(=\)	\(\displaystyle \frac {n \left({n + 1}\right)} 2\)	\(\displaystyle \)

This concludes the proof.

$\blacksquare$

Direct Proof by using Recursion

Let:

$\displaystyle S \left({n}\right) = 1 + 2 + \cdots + n = \sum_{i=1}^n i$

Then:

	\(\displaystyle \)	\(\displaystyle S \left({n}\right)\)	\(=\)	\(\displaystyle n + (n-1) + (n-2) + \cdots + 2 + 1\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle n + (n-1) + (n-2) + \cdots + (n-(n-2)) + (n-(n-1))\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle n^2 - (1 + 2 + \cdots + (n-1))\)	\(\displaystyle \)

Then:

	\(\displaystyle \)	\(\displaystyle S \left({n}\right)\)	\(=\)	\(\displaystyle n^2 - S(n-1)\)	\(\displaystyle \)	Establishes a recursive definition of triangular numbers
	\(\displaystyle \)	\(\displaystyle S \left({n}\right)\)	\(=\)	\(\displaystyle n + S(n-1)\)	\(\displaystyle \)	The standard recursive definition of triangular numbers
	\(\displaystyle \)	\(\displaystyle 2 S \left({n}\right)\)	\(=\)	\(\displaystyle n^2 + n\)	\(\displaystyle \)	Adding the equations together
	\(\displaystyle \)	\(\displaystyle S \left({n}\right)\)	\(=\)	\(\displaystyle \frac{n(n+1)} 2\)	\(\displaystyle \)

$\blacksquare$

Proof by Induction

Base Case

When $n=1$, we have $\displaystyle \sum_{i=1}^1 i = 1$.

Also, $\displaystyle \frac{n \left({n+1}\right)} 2 = \frac {1 \cdot 2} 2 = 1$.

This is our base case.

Induction Hypothesis

$\forall k \in \N: k \ge 1: \displaystyle \sum_{i=1}^k i = \frac {k \left({k+1}\right)} 2$

This is our induction hypothesis.

Induction Step

This is our induction step:

Consider $n = k+1$.

By the properties of summation:

$\displaystyle \sum_{i=1}^{k+1} i = \sum_{i=1}^k i + k + 1$

Using the induction hypothesis this can be simplified to:

	\(\displaystyle \)	\(\displaystyle \frac{k \left({k+1}\right)} 2 + k + 1\)	\(=\)	\(\displaystyle \frac{k \left({k+1}\right) + 2k + 2} 2\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{k^2 + 3k + 2} 2\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{\left({k+1}\right) \left({k+2}\right)} 2\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{\left({k+1}\right) \left({\left({k+1}\right) + 1}\right)} 2\)	\(\displaystyle \)

Thus, the result has been shown by induction.

$\blacksquare$

Proof by Arithmetic Progression

Follows directly from Sum of Arithmetic Progression putting $a = 1$ and $d = 1$.

$\blacksquare$

Proof by Polygonal Numbers

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

Hence from Closed Form for Polygonal Numbers we have that $\displaystyle T_n = \frac {n \left({2 + \left({n-1}\right)\left({k-2}\right)}\right)} 2$ where $k = 3$.

The result follows after some simple algebra.

$\blacksquare$

Proof using Binomial Coefficients

From Properties of Binomial Coefficients: Particular Values, we have that:

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

Thus:

	\(\displaystyle \)	\(\displaystyle \sum_{k=1}^n k\)	\(=\)	\(\displaystyle \sum_{k=1}^n \binom k 1\)	\(\displaystyle \)	Properties of Binomial Coefficients: Particular Values
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \binom {n + 1} 2\)	\(\displaystyle \)	Sum of k Choose m up to n‎
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {\left({n+1}\right) n} 2\)	\(\displaystyle \)	Definition of binomial coefficient

$\blacksquare$

Sources

• Seth Warner: Modern Algebra (1965): $\S 18$: Exercise $18.10 \ \text{(a)}$
• Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.6$: Problem $35$
• For a video presentation of the contents of this page, visit the Khan Academy.