How to use well-ordering principle of natural numbers to prove that $S_n = \frac{n(n+1)}{2}$?

Question

Is it possible to use well-ordering principle of natural numbers to prove the following $S_n = 1+2+3+...+n=\frac{n(n+1)}{2}$, and not really using principle of mathematical induction,is true for all natural numbers?

Answer 1

Yes, it's possible. Here's a start: let $P(n)$ be the statement that $$ S_n = 1 + \ldots n = \frac{n(n+1)}{2}. $$

Suppose that $P(n)$ is not true for some natural number $k$. Then $Q$, the set of all natural numbers for which it's not true, is nonempty (it contains $k$, after all!), and hence has a least element, $b$, by well-ordering. You know that $b$ is not zero, because the statement is true for $n = 0$.

i. What can you say about $b - 1$ ?

ii. What can you say about the truth of the statement for $n = b - 1$?

Use this to arrive at a contradiction.

====

A slightly more elaborate alternate proof is to use well-ordering (as an axiom) to prove the "axiom" of mathematical induction as a theorem, and then write down the inductive proof. :)