1+2+...+n+(n-1)+...+1 = n^2/Proof 3

From ProofWiki
Jump to navigation Jump to search

Theorem

$\forall n \in \N: 1 + 2 + \cdots + n + \left({n-1}\right) + \cdots + 1 = n^2$


Proof

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 + \left({k - 1}\right) + \cdots + 1 = k^2$

Now we need to show true for $n=k+1$:

$1 + 2 + \cdots + \left({k + 1}\right) + k + \left({k - 1}\right) + \cdots + 1 = \left({k + 1}\right)^2$


Induction Step

This is our induction step:

\(\displaystyle \) \(\) \(\displaystyle 1 + 2 + \cdots + \left({k + 1}\right) + k + \left({k - 1}\right) + \cdots + 1\)
\(\displaystyle \) \(=\) \(\displaystyle \left({1 + 2 + \cdots + k + \left({k - 1}\right) + \cdots + 1}\right) + k + \left({k + 1}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle k^2 + k + \left({k + 1}\right)\) from induction hypothesis
\(\displaystyle \) \(=\) \(\displaystyle k^2 + 2k + 1\)
\(\displaystyle \) \(=\) \(\displaystyle \left({k + 1}\right)^2\)

The result follows by induction.

$\blacksquare$