1+2+...+n+(n-1)+...+1 = n^2
Jump to navigation
Jump to search
Theorem
- $\forall n \in \N: 1 + 2 + \cdots + n + \paren {n - 1} + \cdots + 1 = n^2$
Direct Proof 1
| \(\ds \) | \(\) | \(\ds 1 + 2 + \cdots + \paren {n - 1} + n + \paren {n - 1} + \cdots + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 1 + 2 + \cdots + \paren {n - 1} + \paren {n - 1} + \cdots + 1 + n\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 2 \paren {1 + 2 + \cdots + \paren {n - 1} } + n\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 2 \paren {\frac {\paren {n - 1} n} 2} + n\) | Closed Form for Triangular Numbers | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {n - 1} n + n\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds n^2 - n + n\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds n^2\) |
$\blacksquare$
Direct Proof 2
| \(\ds \) | \(\) | \(\ds 1 + 2 + \cdots + \paren {n - 1} + n + \paren {n - 1} + \cdots + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {1 + 2 + \cdots + \paren {n - 1} } + \paren {1 + 2 + \cdots + \paren {n - 1} + n}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \frac {\paren {n - 1} n} 2 + \frac {n \paren {n + 1} } 2\) | Closed Form for Triangular Numbers | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac {n^2 - n + n^2 + n} 2\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds n^2\) |
$\blacksquare$
Proof by Induction
Proof by induction:
Basis for the Induction
$n = 1$ holds trivially.
Just to make sure, we try $n = 2$:
- $1 + 2 + 1 = 4$
Likewise $n^2 = 2^2 = 4$.
So shown for basis for the induction.
Induction Hypothesis
This is our induction hypothesis:
- $1 + 2 + \cdots + k + \paren {k - 1} + \cdots + 1 = k^2$
Now we need to show true for $n = k + 1$:
- $1 + 2 + \cdots + \paren {k + 1} + k + \paren {k - 1} + \cdots + 1 = \paren {k + 1}^2$
Induction Step
This is our induction step:
| \(\ds \) | \(\) | \(\ds 1 + 2 + \cdots + \paren {k + 1} + k + \paren {k - 1} + \cdots + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {1 + 2 + \cdots + k + \paren {k - 1} + \cdots + 1} + k + \paren {k + 1}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds k^2 + k + \paren {k + 1}\) | from induction hypothesis | |||||||||||
| \(\ds \) | \(=\) | \(\ds k^2 + 2k + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {k + 1}^2\) |
The result follows by induction.
$\blacksquare$
Proof 4
Let $T_n = 1 + 2 + \cdots + n + \left({n - 1}\right) + \cdots + 1$.
We have $T_1 = 1$
and
| \(\ds T_n - T_{n-1}\) | \(=\) | \(\ds \left({1 + 2 + \cdots + n + \left({n - 1}\right) + \cdots + 1 }\right)\) | Definition of $T_n$ | |||||||||||
| \(\ds \) | \(\) | \(\, \ds - \, \) | \(\ds \left({1 + 2 + \cdots + \left({n - 1}\right) + \left({n - 2}\right) + \cdots + 1}\right)\) | |||||||||||
| \(\ds \) | \(=\) | \(\ds \left({\left({1 + 2 + \cdots + n}\right) - \left({1 + 2 + \cdots + \left({n - 1}\right)}\right)}\right)\) | Integer Addition is Associative | |||||||||||
| \(\ds \) | \(\) | \(\, \ds + \, \) | \(\ds \left({\left({\left({n - 1}\right) + \left({n - 2}\right) + \cdots + 1}\right) - \left({\left({n - 2}\right) + \left({n - 3}\right) + \cdots + 1}\right)}\right)\) | Integer Addition is Commutative | ||||||||||
| \(\ds \) | \(=\) | \(\ds n + \left({n - 1}\right)\) | simplifying | |||||||||||
| \(\ds \) | \(=\) | \(\ds 2 n - 1\) |
Thus we have:
| \(\ds T_n\) | \(=\) | \(\ds \left({T_n - T_{n-1} }\right) + \left({T_{n-1} - T_{n-2} }\right) + \cdots + \left({T_2 - T_1}\right) + T_1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \left({2 n - 1}\right) + \left({2 \left({n - 1}\right) - 1}\right) + \cdots + \left({2 \times 2 - 1}\right) + 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 1}^n 2 k - 1\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds n^2\) | Odd Number Theorem |
$\blacksquare$
Illustration
Sources
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $25$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $25$