1+2+...+n+(n-1)+...+1 = n^2

From ProofWiki
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 the 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 the 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 + \paren {n - 1} + \cdots + 1$.

We have $T_1 = 1$

and

\(\ds T_n - T_{n - 1}\) \(=\) \(\ds \paren {1 + 2 + \cdots + n + \paren {n - 1} + \cdots + 1 }\) Definition of $T_n$
\(\ds \) \(\) \(\, \ds - \, \) \(\ds \paren {1 + 2 + \cdots + \paren {n - 1} + \paren {n - 2} + \cdots + 1}\)
\(\ds \) \(=\) \(\ds \paren {\paren {1 + 2 + \cdots + n} - \paren {1 + 2 + \cdots + \paren {n - 1} } }\) Integer Addition is Associative
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \paren {\paren {\paren {n - 1} + \paren {n - 2} + \cdots + 1} - \paren {\paren {n - 2} + \paren {n - 3} + \cdots + 1} }\) Integer Addition is Commutative
\(\ds \) \(=\) \(\ds n + \paren {n - 1}\) simplifying
\(\ds \) \(=\) \(\ds 2 n - 1\)

Thus we have:

\(\ds T_n\) \(=\) \(\ds \paren {T_n - T_{n - 1} } + \paren {T_{n - 1} - T_{n - 2} } + \cdots + \paren {T_2 - T_1} + T_1\)
\(\ds \) \(=\) \(\ds \paren {2 n - 1} + \paren {2 \paren {n - 1} - 1} + \cdots + \paren {2 \times 2 - 1} + 1\)
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^n 2 k - 1\)
\(\ds \) \(=\) \(\ds n^2\) Odd Number Theorem

$\blacksquare$


Illustration

1plus2plusnplus2plus1.png


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=1%2B2%2B...%2Bn%2B(n-1)%2B...%2B1_%3D_n%5E2&oldid=494717"