Triangular Number as Alternating Sum and Difference of Squares
Jump to navigation
Jump to search
Theorem
\(\ds \forall n \in \N: \, \) | \(\ds \frac {n \paren {n + 1} } 2\) | \(=\) | \(\ds \sum_{j \mathop = 0}^{n - 1} \paren {-1}^j \paren {n - j}^2\) | |||||||||||
\(\ds \) | \(=\) | \(\ds n^2 - \paren {n - 1}^2 + \paren {n - 2}^2 - \cdots + \paren {-1}^{n - 1}\) |
Thus the $n$th triangular number can be expressed as the alternating sum and difference of squares:
So:
\(\ds 1\) | \(=\) | \(\ds 1^2\) | ||||||||||||
\(\ds 3\) | \(=\) | \(\ds 2^2 - 1^2\) | ||||||||||||
\(\ds 6\) | \(=\) | \(\ds 3^2 - 2^2 + 1^2\) | ||||||||||||
\(\ds 10\) | \(=\) | \(\ds 4^2 - 3^2 + 2^2 - 1^2\) |
and so on.
Proof
The proof proceeds by induction.
For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:
- $\ds \frac {n \paren {n + 1} } 2 = \sum_{j \mathop = 0}^{n - 1} \paren {-1}^j \paren {n - j}^2$
Basis for the Induction
$\map P 1$ is the case:
\(\ds \frac {n \paren {n + 1} } 2\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1^2\) |
which is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
- $\ds \frac {k \paren {k + 1} } 2 = \sum_{j \mathop = 0}^{k - 1} \paren {-1}^j \paren {n - j}^2$
from which it is to be shown that:
- $\ds \frac {\paren {k + 1} \paren {k + 2} } 2 = \sum_{j \mathop = 0}^k \paren {-1}^j \paren {k - j + 1}^2$
Induction Step
This is the induction step:
\(\ds \sum_{j \mathop = 0}^k \paren {-1}^j \paren {k - j + 1}^2\) | \(=\) | \(\ds \paren {k + 1}^2 - \paren {\sum_{j \mathop = 0}^{k - 1} \paren {-1}^j \paren {n - j}^2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {k + 1}^2 - \frac {k \paren {k + 1} } 2\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {2 k^2 + 4 k + 2 - k^2 - k} 2\) | multiplying everything out | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {k^2 + 3 k + 2} 2\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {k + 1} \paren {k + 2} } 2\) | factoring |
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
$\blacksquare$
Sources
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $15$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction: Exercise $7$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $15$