Closed Form for Triangular Numbers/Proof by Induction

From ProofWiki
Jump to navigation Jump to search

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

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$


Also see

This is usually the first proof by induction that a student mathematician encounters.

The second one is often Proof by Induction of Sum of Sequence of Squares.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Closed_Form_for_Triangular_Numbers/Proof_by_Induction&oldid=614087"