Closed Form for Triangular Numbers/Proof by Recursion

From ProofWiki
Jump to navigation Jump to 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$


Proof

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$