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 $\displaystyle \frac {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}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \paren {1 + 2 + \dotsb + \paren {n - 1} + n} + \paren {n + \paren {n - 1} + \dotsb + 2 + 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \paren {1 + n} + \paren {2 + \paren {n - 1} } + \dotsb + \paren {\paren {n - 1} + 2} + \paren {n + 1}\) $\quad$ Integer Addition is Commutative, Integer Addition is Associative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \paren {n + 1}_1 + \paren {n + 1}_2 + \dotsb + \paren {n + 1}_n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n \paren {n + 1}\) $\quad$ $\quad$

So:

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

$\blacksquare$


Proof by Telescoping Sum

Observe that:

\(\displaystyle \sum_{i \mathop = 1}^n \left({\left({i + 1}\right)^2 - i^2}\right)\) \(=\) \(\displaystyle -\sum_{i \mathop = 1}^n \left({i^2 - \left({i + 1}\right)^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle - \left({1 - \left({n + 1}\right)^2}\right)\) $\quad$ Telescoping Series $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({n + 1}\right)^2 - 1\) $\quad$ $\quad$

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 n + 2 \sum_{i \mathop = 1}^n \, i\) \(=\) \(\displaystyle n^2 + 2 n\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle 2 \sum_{i \mathop = 1}^n \, i\) \(=\) \(\displaystyle n \left({n + 1}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n \, i\) \(=\) \(\displaystyle \frac {n \left({n + 1}\right)} 2\) $\quad$ $\quad$

This concludes the proof.

$\blacksquare$


Proof by Recursion

Let:

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

Thus:

\(\displaystyle S \left({n}\right)\) \(=\) \(\displaystyle n + \left({n - 1}\right) + \left({n - 2}\right) + \cdots + 2 + 1\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n + \left({n - 1}\right) + \left({n - 2}\right) + \cdots + \left({n - \left({n - 2}\right)}\right) + \left({n - \left({n - 1}\right)}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \underbrace{n + n + \cdots + n}_{n \text { times} }\) $\quad$ extracting $n$ from each term $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({- 1}\right) + \left({- 2}\right) + \cdots + \left({- \left({n - 2}\right)}\right) + \left({- \left({n - 1}\right)}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n^2 - \left({1 + 2 + \cdots + \left({n - 1}\right)}\right)\) $\quad$ $\quad$
\((1):\quad\) \(\displaystyle \implies \ \ \) \(\displaystyle S \left({n}\right)\) \(=\) \(\displaystyle n^2 - S \left({n - 1}\right)\) $\quad$ $\quad$


Then:

\((2):\quad\) \(\displaystyle S \left({n}\right)\) \(=\) \(\displaystyle n + S \left({n - 1}\right)\) $\quad$ Definition of Triangular Number $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle 2 S \left({n}\right)\) \(=\) \(\displaystyle n^2 + n\) $\quad$ $(1) + (2)$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle S \left({n}\right)\) \(=\) \(\displaystyle \frac {n \left({n + 1}\right)} 2\) $\quad$ $\quad$

$\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\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {k^2 + 3 k + 2} 2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {k + 1} \paren {k + 2} } 2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {k + 1} \paren {\paren {k + 1} + 1} } 2\) $\quad$ $\quad$


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

$\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)\) $\quad$ Closed Form for Polygonal Numbers $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac n 2 \left({n + 1}\right)\) $\quad$ $\quad$

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\) $\quad$ Binomial Coefficient with One $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom {n + 1} 2\) $\quad$ Sum of k Choose m up to n‎ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\left({n+1}\right) n} 2\) $\quad$ Definition of Binomial Coefficient $\quad$

$\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^*}\) $\quad$ $\quad$
\(\displaystyle A \cap B\) \(=\) \(\displaystyle \set {\tuple {a, b}: a = b: a, b \in \N_n^*}\) $\quad$ $\quad$

Thus:

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

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\) $\quad$ Definition of $T_n$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop \in \N_n^*} i\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop \in \N_n^*} \size {\set {a: a \in \N_i^*} }\) $\quad$ Count of Finite Set,Definition of Initial Segment of One-Based Natural Numbers $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \size {\set {\tuple {a, i} :a\in \N_i^*, i \in \N_n^*} }\) $\quad$ Inclusion-Exclusion Principle, sets are mutually exclusive as their second argument in the ordered pair are different $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \size {\set {\tuple {a, b}: a \le b, a, b \in \N_n^*} }\) $\quad$ Change of Variable, Definition of Initial Segment of One-Based Natural Numbers $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \size A\) $\quad$ Definition of $A$ $\quad$

$\blacksquare$


Proof using Odd Number Theorem

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

$\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\) $\quad$ $\quad$
\(\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!}\) $\quad$ $\quad$

where $B_k$ are the Bernoulli numbers.


Setting $p = 1$:

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

Hence the result.

$\blacksquare$


Also see

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


Historical Note

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.


Sources