Closed Form for Triangular Numbers

From ProofWiki
Jump to: navigation, search


Theorem

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

$\displaystyle 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:

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

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

Then:

\(\displaystyle 2 \sum_{i \mathop = 1}^n i\) \(=\) \(\displaystyle 2 \paren {1 + 2 + \dotsb + \paren {n - 1} + n}\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {1 + 2 + \dotsb + \paren {n - 1} + n} + \paren {n + \paren {n - 1} + \dotsb + 2 + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \paren {n + 1}_1 + \paren {n + 1}_2 + \dotsb + \paren {n + 1}_n\)
\(\displaystyle \) \(=\) \(\displaystyle n \paren {n + 1}\)

So:

\(\displaystyle 2 \sum_{i \mathop = 1}^n i\) \(=\) \(\displaystyle n \paren {n + 1}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n i\) \(=\) \(\displaystyle \frac {n \paren {n + 1} } 2\)

$\blacksquare$


Proof by Telescoping Sum

Observe that:

\(\displaystyle \sum_{i \mathop = 1}^n \paren {\paren {i + 1}^2 - i^2}\) \(=\) \(\displaystyle -\sum_{i \mathop = 1}^n \paren {i^2 - \paren {i + 1} ^2}\)
\(\displaystyle \) \(=\) \(\displaystyle -\paren {1 - \paren {n + 1}^2}\) Telescoping Series
\(\displaystyle \) \(=\) \(\displaystyle \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:

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

This concludes the proof.

$\blacksquare$


Proof by Recursion

We have that:

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

Thus:

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


Then:

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

$\blacksquare$


Proof by Induction

Proof by induction:

Basis for the Induction

When $n = 1$, we have:

$\displaystyle \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: \displaystyle \sum_{i \mathop = 1}^k i = \frac {k \paren {k + 1} } 2$

This is our induction hypothesis.

It is to be demonstrated that:

$\displaystyle \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:

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

Using the induction hypothesis this can be simplified to:

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


Hence the result by induction.

$\blacksquare$


Proof by Arithmetic Progression

\(\displaystyle \sum_{i \mathop = 0}^{m - 1} \left({a + i d}\right)\) \(=\) \(\displaystyle m \left({a + \frac {m - 1} 2 d}\right)\) Sum of Arithmetic Progression
\(\displaystyle \sum_{i \mathop = 0}^n \left({a + i d}\right)\) \(=\) \(\displaystyle \left({n + 1}\right) \left({a + \frac n 2 d}\right)\) Let $n = m - 1$
\(\displaystyle \sum_{i \mathop = 0}^n i\) \(=\) \(\displaystyle \left({n + 1}\right) \left({\frac n 2}\right)\) Let $a = 0$ and $d = 1$
\(\displaystyle 0 + \sum_{i \mathop = 1}^n i\) \(=\) \(\displaystyle \frac {n \left({n+1}\right)} 2\)
\(\displaystyle \sum_{i \mathop = 1}^n i\) \(=\) \(\displaystyle \frac {n \left({n+1}\right)} 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:

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

Hence the result.

$\blacksquare$


Proof using Binomial Coefficients

From Binomial Coefficient with One:

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

Thus:

\(\displaystyle \sum_{k \mathop = 1}^n k\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^n \binom k 1\) Binomial Coefficient with One
\(\displaystyle \) \(=\) \(\displaystyle \binom {n + 1} 2\) Sum of k Choose m up to n‎
\(\displaystyle \) \(=\) \(\displaystyle \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:

\(\displaystyle A \cup B\) \(=\) \(\displaystyle \set {\tuple {a, b}: a, b \in \N_n^*}\)
\(\displaystyle A \cap B\) \(=\) \(\displaystyle \set {\tuple {a, b}: a = b: a, b \in \N_n^*}\)

Thus:

\(\displaystyle \size A + \size B\) \(=\) \(\displaystyle \size {A \cup B} + \size {A \cap B}\) Inclusion-Exclusion Principle
\(\displaystyle \) \(=\) \(\displaystyle 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$
\(\displaystyle T_n\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n i\) Definition of $T_n$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop \in \N_n^*} i\)
\(\displaystyle \) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \size A\) Definition of $A$

$\blacksquare$


Proof using Odd Number Theorem

\(\displaystyle \sum_{j \mathop = 1}^n \left({2j - 1}\right)\) \(=\) \(\displaystyle n^2\) Odd Number Theorem
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_{j \mathop = 1}^n \left({2j - 1}\right) + \sum_{j \mathop = 1}^n 1\) \(=\) \(\displaystyle n^2 + n\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_{j \mathop = 1}^n \left({2 j}\right)\) \(=\) \(\displaystyle n \left({n + 1}\right)\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum_{j \mathop = 1}^n j\) \(=\) \(\displaystyle \frac {n \left({n + 1}\right)} 2\)

$\blacksquare$


Proof using Bernoulli Numbers

From Sum of Powers of Positive Integers:

\(\displaystyle \sum_{i \mathop = 1}^n i^p\) \(=\) \(\displaystyle 1^p + 2^p + \cdots + n^p\)
\(\displaystyle \) \(=\) \(\displaystyle \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$:

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

Hence the result.

$\blacksquare$


Also see

$\displaystyle \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.


Sources