Solution

Use the Well Ordering Principle to prove that the following statement is true for all positive integers $n$: $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$


We argue indirectly. Assume this statement is false for at least one positive integer $n$.

Now, let $S$ be the set defined by $$S = \left\{n \in \mathbb{Z}^+ \textrm{ such that } \sum_{i=1}^n i \neq \frac{n(n+1)}{2} \right\}$$ $S$ is non-empty by our assumption, and contains only non-negative values of $n$, so the well-ordering principle applies, and guarantees that $S$ has a least element.

Suppose we call this least element $k$.

Remember, $0 \notin S$ since $0 \notin \mathbb{Z}^+$.

Also, $1 \notin S$, as simply plugging in $n=1$ into the left and right hand sides of the statement reveals it is true for this value of $n$.

Thus $k$, which is in $S$, must be greater than $1$.

However, if $k > 1$, then $k-1$ is a non-negative integer less than $k$, the minimum value for which our statement is false. Consequently, the statement must be true when $n=k-1$.

Hence, $$\sum_{i=1}^{k-1} i = \frac{(k-1)((k-1)+1)}{2} = \frac{k(k-1)}{2}$$

Importantly, knowing this allows us to investigate the validity of the statement when $n=k$ from another direction.

Consider the following sum, $$\begin{array}{rcl} \sum_{i=1}^k i &=& \left[ \sum_{i=1}^{k-1} i \right] + k\\\\ &=& \frac{k(k-1)}{2} + k\\\\ &=& \frac{k^2 - k}{2} + \frac{2k}{2}\\\\ &=& \frac{k^2 + k}{2}\\\\ &=& \frac{k(k+1)}{2} \end{array}$$

But this means that the statement is true when $n=k$, which contradicts $k$ being the least integer for which the statement is false.

Having reached a contradiction, it must be the case that the opposite of our assumption is true. Hence, the statement $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$ is true for every positive integer $n$.